### Is n prime?

#### By jmcp-Oracle on Apr 05, 2005

While I was finding the right path to travel with my assignment, I figured
out a fairly efficient method of calculating whether

*n*is prime or not:unsigned int prime(unsigned it ofn) { /\* \* :: returns 1 if ofn is prime, 0 otherwise \* \* precondition: ofn > 0 \*/ unsigned int root; /\* |_sqrt(ofn)_| \*/ unsigned int count; unsigned int mark = 1; /\* our boundary condition var \*/ /\* we only need to go to floor(sqrt(ofn)) \*/ root = (unsigned int)floor(sqrt(ofn)); for (count = 2; count <= root; count++) { if (!(ofn % count)) { /\* not prime, so escape out \*/ mark--; break; } } return (mark); }How much more efficient could I get with this routine?

This is an old chestnut, going back to the ancient Greeks. Google on "Eratosthenes sieve".

do 2 as a special case then start the loop at 3 and increment by 2. Saves half the divisions.

next, do 2 and 3 as special cases. start the loop at 5 and increment by 6. test only count and count+2 in the loop, since count+1, count+3, count+4 and count+5 are all divisible by 2 or 3 (proof left to reader.) Now you're only testing 1/3 of the divisors, and you've "unrolled" the loop so the loop overhead is amortized over two checks instead of just one.

technique can be extended but with rapidly diminishing returns (next step is to increment by 30 and test only 8 of the 30 numbers in each increment -- that only drops from .333 to .266)

further speedups possible but require some fairly exotic number theory results

Posted by

Rich McAllisteron April 05, 2005 at 04:05 AM EST #really, really keento engage in intellectual jousting like this. I love it and would not give it up for anything.Posted by

James McPhersonon April 05, 2005 at 04:32 AM EST #Nice write up, it will be good to know as a software release engineer as well... time to review the makefiles that I maintain. Also, do you have any thoughts on why java would be running slower on sparc/solaris vs. opteron/solaris or xeon/linux? I have a simple sorting program that is

whickedfast on the amd box we have and burries the sparc box I was running on.dl

Posted by

Dan Lacheron April 05, 2005 at 03:13 PM EST #Posted by

Ben Cooperon April 07, 2005 at 04:47 PM EST #