Help with Prime Bits function

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
wtt
Forum Newbie
Posts: 8
Joined: Tue Mar 27, 2007 4:43 pm

Help with Prime Bits function

Post by wtt »

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.
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

Please do not duplicate your thread again, ever.
wtt
Forum Newbie
Posts: 8
Joined: Tue Mar 27, 2007 4:43 pm

THere is no proper forum

Post by wtt »

feyd wrote:Please do not duplicate your thread again, ever.
So I put it to two different ones to give the problem larger exposure...

Unlucky, you saw both of them... :(
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

Are you asking PHP questions? The function signature you posted is for something based in C.
wtt
Forum Newbie
Posts: 8
Joined: Tue Mar 27, 2007 4:43 pm

It could be implement in php,right?

Post by wtt »

feyd wrote:Are you asking PHP questions? The function signature you posted is for something based in C.
Language is not issue. The bottleneck here is how to solve this problem with programming language.

Since I'd like to learn Php, so I post here, and hope some guru can help me a little bit...
User avatar
stereofrog
Forum Contributor
Posts: 386
Joined: Mon Dec 04, 2006 6:10 am

Post by stereofrog »

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).
Post Reply