Historically, the most efficient way to find all of the small primes (say all those less than
10,000,000) is by using the Sieve of Eratosthenes(ca 240 BC):
Make a list of all the integers less than or equal to n (and
greater than one). Strike out the multiples of all primes less than or equal to
the square root of n,
then the numbers that are left are the primes. For an example (as
well as additional information and pseudocode), see the Prime Glossary's entry
on the sieve of
Eratosthenes .
The article [Pritchard87] offers
comparisons of various sieves. Below we offer a list of implementations of the
sieve without any such comparisons (in fact, I've not even tried most of these
out).
|
