Scott Hanselman

Prime Pattern

August 29, '06 Comments [5] Posted in Musings
Sponsored By

Anyone out there understand Prime Math or know a Math Professor who does?

Danny Cooper at Aspose says he has a prime pattern. He says it's 100% to 150% faster than the well-known Sieve of Eratosthenes. Email him if you want his code projects.

Now playing: Stephen Lynch - Superhero

About Scott

Scott Hanselman is a former professor, former Chief Architect in finance, now speaker, consultant, father, diabetic, and Microsoft employee. He is a failed stand-up comic, a cornrower, and a book author.

facebook twitter subscribe
About   Newsletter
Sponsored By
Hosting By
Dedicated Windows Server Hosting by ORCS Web
Tuesday, August 29, 2006 6:34:20 PM UTC
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!
Tuesday, August 29, 2006 7:16:48 PM UTC
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.
Tuesday, August 29, 2006 10:14:49 PM UTC
I think Craig is referring to Mersenne primes. http://mathworld.wolfram.com/MersennePrime.html
Wednesday, August 30, 2006 2:02:40 AM UTC
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.
Alex Lyman
Wednesday, August 30, 2006 1:16:18 PM UTC
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.
Comments are closed.

Disclaimer: The opinions expressed herein are my own personal opinions and do not represent my employer's view in any way.