Hello everyone,
I encountered this problem from a company's job seeking website. I am a newbit to PHP field, but I would really like to learn this language since it is so popular in the web application development field. Could you kindly to help me get started? Thanks a lot.
Prime Bits
First, consider a function P(x) where:
P(x) returns:
true if the number of 1 bits set in the
binary representation of x is prime,
false otherwise.
For example, P(239) returns true, while P(51) returns false.
Next, consider the following function prime_bits:
uint64_t prime_bits(uint64_t a, uint64_t b);
A call to prime_bits(a, b) returns the number of values between a and b inclusive for which P(x) is true. For example, prime_bits(4, 10) returns 5. Your job is to implement the prime_bits function.
Your implementation should be efficient, and it should be wrapped up nicely such that one can specify a and b on the commandline when running your program. You may expect the range of a and b to be limited to non-negative 64-bit integers, though it would certainly be uncouth for your algorithm to break down for larger values.
Help with Prime Bits function
Moderator: General Moderators
THere is no proper forum
So I put it to two different ones to give the problem larger exposure...feyd wrote:Please do not duplicate your thread again, ever.
Unlucky, you saw both of them...
It could be implement in php,right?
Language is not issue. The bottleneck here is how to solve this problem with programming language.feyd wrote:Are you asking PHP questions? The function signature you posted is for something based in C.
Since I'd like to learn Php, so I post here, and hope some guru can help me a little bit...
- stereofrog
- Forum Contributor
- Posts: 386
- Joined: Mon Dec 04, 2006 6:10 am
Calculate the number of bits (see http://infolab.stanford.edu/~manku/bitc ... count.html), then find if the number is prime using lookup table (because there are only 18 primes lesser than 64).