View Single Post
Old 2009-09-23, 18:20   #3
bsquared's Avatar
Feb 2007

2·1,789 Posts

Originally Posted by storm5510 View Post
... an application that could find prime numbers, in general. No specific types. ...
Well, this isn't really my specialty, but I think I know this much: it really depends a lot on how big of prime numbers you want to find.

You can use a sieve to find ALL prime numbers up to several billion in a few seconds.

You can use these primes to test numbers up to about 20 digits long in a few more seconds, using the naive approach.

Anything much more than that and you have to start using quite a bit more math involved in general purpose primalty proving algorithms, because the number of divisions to perform grows to quickly to continue using the naive approach.

General purpose primalty proving algorithm include the APRCL test and ECPP (probably others). Even with these tests, you'd be doing great to be able to prove primes up to a couple thousand digits. Any bigger than that, and you're only hope is that the number has a special form and corresponding prime proving algorithm (Mersenne's, Fermat's). That's where my usefullness (such as it is) stops.

Last fiddled with by bsquared on 2009-09-23 at 18:44 Reason: elaborate a bit on general purpose tests...
bsquared is offline   Reply With Quote