Scott Hanselman's ComputerZen.com

I'm just curious how something can be 100% faster, let alone 150% faster. Wouldn't that mean it completes is zero or negative time? :-)

Sounds neat though!

This is almost certainly completely useless. I haven't applied any mathematic rigor to it (my math chops may no longer be up to it in fact) but I'd be about willing to bet my mortgage against this being useful for anything but tiny prime numbers...like the Sieve of Erasthenes. Note that in both cases the number of things you have to keep track of goes up by one for every prime. I bet his pattern is essentially unintelligible by the time you get much past 1000.

I'm also willing to bet that a base 30 examination shows similar repitition...probably even better, because 6 = 2*3, but 30 = 2*3*5, i.e. it has more primes in it.

The best way of finding prime numbers that I know of uses an algorithm I first found in Bruce Schneier's "Applied Cryptography". The exact details escape my memory, but basically you wind up iterating n times and proving that a given number is prime with a probability of something like 1 in 2^n.

Small prime numbers are only interesting for grade school math.

I think Craig is referring to Mersenne primes. http://mathworld.wolfram.com/MersennePrime.html

While I've never actually seen somebody go through and color tables with these thing, this is pretty much common knowledge. The first part (P ?= 6n ± 1) is basically what you get when you apply the Sieve of Eratosthenes with the primes 2 and 3. The second part (the 'skips') is just the Sieve of Eratosthenes past that point. I could definitly see a clear speed increase happening when the number of primes you've applied the sieve to is small -- what it comes down to is O(n) compared to O(n-2) -- negligible when n gets larger.

There are different kind of algorithms for calculating prime numbers.

You may want to enumerate all primes. You may want to find just one prime, say near to a given integer. Or you may want to find a very big prime.

Testing a number if it is prime or not takes a long time. A useful concept therefore is that of pseudo primes (see http://en.wikipedia.org/wiki/Pseudoprimes), where you apply a condition that is only true for primes, but can be computed faster than the real test. Then you have to apply the real test only on those numbers that pass the pseudo prime test. The given algorithm is just a trivial pseudo prime test, as Alex correctly pointed out.