Prime Pattern
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.
About Newsletter
Hosting By
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'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.
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.
Sounds neat though!