Eratosthenes (276-194 B.C.) was a librarian in the library of Alexandria. He is known for determining the circumference of the Earth and estimating the distances to the sun and the moon. He is also credited (in the Introduction to Arithmetic by Nicomachus) for an algorithm to determine the prime numbers in the sequence of integers 1 to N, where N is a larger positive integer. This algorithm is known as the "Sieve of Eratosthenes" because it sequentially filters out the multiples of known primes as therefore being non-prime.
To find all prime numbers below a given number N:
Write all integers from 1 through N in order;
Eliminate 1 as it is a not a prime number by definition;
Alternatively (commonly), skip step 2 by omitting the integer 1 when initialising the list with integers 2..N;
Repeat the following steps until the next found prime is greater than the square root of N;
find the next number not yet eliminated (initially 2, then 3, then 5, etc.);
mark this number as prime;
eliminate all of its remaining multiples (means checking for multiples already eliminated);
All the non-eliminated numbers in the list must be prime.
The number after the previous prime is also a prime. Multiply each number in the list starting from
the latest prime by the latest prime and discard the products (3x3, 3x5, 3x7, 3x9, 3x11):
2 3 5 7 11 13 17 19 23 25 29 31 35...
Repeat step 3. indefinitely. On each repetition a new prime is identified (marked ^) and its multiples eliminated (5x5, 5x7) until all the primes in the starting list have been found:
2 3 5 7 11 13 17 19 23 29 31 ...
When we have exceeded the square root of the upper limit of our range, we have the desired sequence of prime numbers. In the example given above that will be achieved when we identify the prime '7', to give our list of all primes less than 36.
Theoretically, these "sieve" algorithms could run over unlimited (infinite) numbers. Obviously, in practice, they are not scalable as the computational power required for multiplying rapidly increasing values is a serious limitation for finding prime numbers above say 10 million. Consider also that a typical 32 bit computer has a native unsigned integer limit of 4294967295, which has a square root of 65536 (rounded up integer).
This page is best viewed in a web browser that fully supports style sheets (CSS2). You will be able to view the content of this page in your current browser but some aspects may not be optimally rendered.