The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes (below 10 million or so).[3] It is named after Eratosthenes of Cyrene, a Greek mathematician; although none of his works have survived, the sieve was described and attributed to Eratosthenes in the Introduction to Arithmetic by Nicomachus.
Sift the Two's and Sift the Three's,
The Sieve of Eratosthenes.
When the multiples sublime,
The numbers that remain are Prime.
A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself.
To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:
When the algorithm terminates, all the numbers in the list that are not marked are prime.
The main idea here is that every value for p is prime, because we have already marked all the multiples of the numbers less than p.
As a refinement, it is sufficient to mark the numbers in step 3 starting from p2, as all the smaller multiples of p will have already been marked at that point. This means that the algorithm is allowed to terminate in step 4 when p2 is greater than n.
Another refinement is to initially list odd numbers only, (3, 5, ..., n), and count up using an increment of 2p in step 3, thus marking only odd multiples of p greater than p itself. This actually appears in the original algorithm. This can be generalized with wheel factorization, forming the initial list only from numbers coprime with the first few primes and not just from odds, i.e. numbers coprime with 2.
An incremental formulation of the sieve generates primes indefinitely (i.e. without an upper bound) by interleaving the generation of primes with the generation of their multiples (so that primes can be found in gaps between the multiples), where the multiples of each prime p are generated directly, by counting up from the square of the prime in increments of p(or 2p for odd primes).
Trial division can be used to produce primes by filtering out the composites found by testing each candidate number for divisibility by its preceding primes. It is often confused with the sieve of Eratosthenes, although the latter directly generates the composites instead of testing for them. Trial division has worse theoretical complexity than that of the sieve of Eratosthenes in generating ranges of primes.
When testing each candidate number, the optimal trial division algorithm uses just those prime numbers not exceeding its square root. The widely known 1975 functional code byDavid Turner is often presented as an example of the sieve of Eratosthenes but is actually a sub-optimal trial division algorithm.
Time complexity in the random access machine model is operations, a direct consequence of the fact that the prime harmonic series asymptotically approaches
.
The bit complexity of the algorithm is bit operations with a memory requirement of
.
The segmented version of the sieve of Eratosthenes, with basic optimizations, uses operations and
bits of memory.