Sieve of Eratosthenes

Sieve of Eratosthenes: algorithm steps for primes below 121 (including optimization of starting from prime's square).

In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.

It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime.<ref name="horsley">Horsley, Rev. Samuel, F. R. S., "Template:Lang or, The Sieve of Eratosthenes. Being an account of his method of finding all the Prime Numbers," Philosophical Transactions (1683–1775), Vol. 62. (1772), pp. 327–347.</ref> This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.<ref name="ONeill" /> Once all the multiples of each discovered prime have been marked as composites, the remaining unmarked numbers are primes.

The earliest known reference to the sieve (Template:Langx, kóskinon Eratosthénous) is in Nicomachus of Gerasa's Introduction to Arithmetic,<ref name=nicomachus>Template:Citation</ref> an early 2nd century CE book which attributes it to Eratosthenes of Cyrene, a 3rd century BCE Greek mathematician, though describing the sieving by odd numbers instead of by primes.<ref name=nicomachus1926>Template:Citation</ref>

One of a number of prime number sieves, it is one of the most efficient ways to find all of the smaller primes. It may be used to find primes in arithmetic progressions.<ref>J. C. Morehead, "Extension of the Sieve of Eratosthenes to arithmetical progressions and applications", Annals of Mathematics, Second Series 10:2 (1909), pp. 88–104.</ref>

Overview

Template:Quote box

A prime number is a natural number that has exactly two distinct natural number divisors: the number 1 and itself.

To find all the prime numbers less than or equal to a given integer Template:Mvar by Eratosthenes' method:

Create a list of consecutive integers from 2 through Template:Mvar: Template:Math.
Initially, let Template:Mvar equal 2, the smallest prime number.
Enumerate the multiples of Template:Mvar by counting in increments of Template:Mvar from Template:Math to Template:Mvar, and mark them in the list (these will be Template:Math; the Template:Mvar itself should not be marked).
Find the smallest number in the list greater than Template:Mvar that is not marked. If there was no such number, stop. Otherwise, let Template:Mvar now equal this new number (which is the next prime), and repeat from step 3.
When the algorithm terminates, the numbers remaining not marked in the list are all the primes below Template:Mvar.

The main idea here is that every value given to Template:Mvar will be prime, because if it were composite it would be marked as a multiple of some other, smaller prime. Note that some of the numbers may be marked more than once (e.g., 15 will be marked both for 3 and 5).

As a refinement, it is sufficient to mark the numbers in step 3 starting from Template:Math, as all the smaller multiples of Template:Mvar will have already been marked at that point. This means that the algorithm is allowed to terminate in step 4 when Template:Math is greater than Template:Mvar.<ref name="horsley" />

Another refinement is to initially list odd numbers only, Template:Math, and count in increments of Template:Math in step 3, thus marking only odd multiples of Template:Mvar. This actually appears in the original algorithm.<ref name="horsley" /><ref name="nicomachus1926" /> 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), and counting in the correspondingly adjusted increments so that only such multiples of Template:Mvar are generated that are coprime with those small primes, in the first place.<ref name="Runciman">Template:Cite journal</ref>

Example

To find all the prime numbers less than or equal to 30, proceed as follows.

First, generate a list of integers from 2 to 30:

 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

The first number in the list is 2; cross out every 2nd number in the list after 2 by counting up from 2 in increments of 2 (these will be all the multiples of 2 in the list):

 2  3 Template:Gray 5 Template:Gray 7 Template:Gray 9 Template:Gray 11 Template:Gray 13 Template:Gray 15 Template:Gray 17 Template:Gray 19 Template:Gray 21 Template:Gray 23 Template:Gray 25 Template:Gray 27 Template:Gray 29 Template:Gray

The next number in the list after 2 is 3; cross out every 3rd number in the list after 3 by counting up from 3 in increments of 3 (these will be all the multiples of 3 in the list):

 2  3 Template:Gray 5 Template:Gray 7 Template:GrayTemplate:GrayTemplate:Gray 11 Template:Gray 13 Template:GrayTemplate:GrayTemplate:Gray 17 Template:Gray 19 Template:GrayTemplate:GrayTemplate:Gray 23 Template:Gray 25 Template:GrayTemplate:GrayTemplate:Gray 29 Template:Gray

The next number not yet crossed out in the list after 3 is 5; cross out every 5th number in the list after 5 by counting up from 5 in increments of 5 (i.e. all the multiples of 5):

 2  3 Template:Gray 5 Template:Gray 7 Template:GrayTemplate:GrayTemplate:Gray 11 Template:Gray 13 Template:GrayTemplate:GrayTemplate:Gray 17 Template:Gray 19 Template:GrayTemplate:GrayTemplate:Gray 23 Template:GrayTemplate:GrayTemplate:GrayTemplate:GrayTemplate:Gray 29 Template:Gray

The next number not yet crossed out in the list after 5 is 7; the next step would be to cross out every 7th number in the list after 7, but they are all already crossed out at this point, as these numbers (14, 21, 28) are also multiples of smaller primes because 7 × 7 is greater than 30. The numbers not crossed out at this point in the list are all the prime numbers below 30:

 2  3     5     7          11    13          17    19          23                29

Algorithm and variants

Pseudocode

The sieve of Eratosthenes can be expressed in pseudocode, as follows:<ref name="sedgewick">Template:Cite book, p. 16.</ref><ref name="intro">Jonathan Sorenson, An Introduction to Prime Number Sieves, Computer Sciences Technical Report #909, Department of Computer Sciences University of Wisconsin-Madison, January 2, 1990 (the use of optimization of starting from squares, and thus using only the numbers whose square is below the upper limit, is shown).</ref>

algorithm Sieve of Eratosthenes is
    input: an integer n > 1.
    output: all prime numbers from 2 through n.

    let A be an array of Boolean values, indexed by integers 2 to n,
    initially all set to true.
    
    for i = 2, 3, 4, ..., not exceeding Template:Math do
        if A[i] is true
            for j = i², i²+i, i²+2i, i²+3i, ..., not exceeding n do
                set A[j] := false

    return all i such that A[i] is true.

This algorithm produces all primes not greater than Template:Mvar. It includes a common optimization, which is to start enumerating the multiples of each prime Template:Mvar from Template:Math. The time complexity of this algorithm is Template:Math,Template:R provided the array update is an Template:Math operation, as is usually the case.

Segmented sieve

As Sorenson notes, the problem with the sieve of Eratosthenes is not the number of operations it performs but rather its memory requirements.Template:R For large Template:Mvar, the range of primes may not fit in memory; worse, even for moderate Template:Mvar, its cache use is highly suboptimal. The algorithm walks through the entire array Template:Mvar, exhibiting almost no locality of reference.

A solution to these problems is offered by segmented sieves, where only portions of the range are sieved at a time.<ref>Crandall & Pomerance, Prime Numbers: A Computational Perspective, second edition, Springer: 2005, pp. 121–24.</ref> These have been known since the 1970s, and work as follows:Template:R<ref>Template:Cite journal</ref>

Divide the range 2 through Template:Mvar into segments of some size Template:Math.
Find the primes in the first (i.e. the lowest) segment, using the regular sieve.
For each of the following segments, in increasing order, with Template:Mvar being the segment's topmost value, find the primes in it as follows:
1. Set up a Boolean array of size Template:Math.
2. Mark as non-prime the positions in the array corresponding to the multiples of each prime Template:Math found so far, by enumerating its multiples in steps of Template:Math starting from the lowest multiple of Template:Math between Template:Math and Template:Mvar.
3. The remaining non-marked positions in the array correspond to the primes in the segment. It is not necessary to mark any multiples of these primes, because all of these primes are larger than Template:Math, as for Template:Math, one has <math>(k\Delta + 1)^2 > (k+1)\Delta</math>.

If Template:Math is chosen to be Template:Math, the space complexity of the algorithm is Template:Math, while the time complexity is the same as that of the regular sieve.Template:R

For ranges with upper limit Template:Math so large that the sieving primes below Template:Math as required by the page segmented sieve of Eratosthenes cannot fit in memory, a slower but much more space-efficient sieve like the pseudosquares prime sieve, developed by Jonathan P. Sorenson, can be used instead.<ref>J. Sorenson, "The pseudosquares prime sieve", Proceedings of the 7th International Symposium on Algorithmic Number Theory. (ANTS-VII, 2006).</ref>

Incremental sieve

An incremental formulation of the sieve<ref name="ONeill">O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes", Journal of Functional Programming, published online by Cambridge University Press 9 October 2008 Template:Doi, pp. 10, 11 (contains two incremental sieves in Haskell: a priority-queue–based one by O'Neill and a list–based, by Richard Bird).</ref> 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 Template:Mvar are generated directly by counting up from the square of the prime in increments of Template:Mvar (or Template:Math for odd primes). The generation must be initiated only when the prime's square is reached, to avoid adverse effects on efficiency. It can be expressed symbolically under the dataflow paradigm as

primes = [2, 3, ...] \ [[p², p²+p, ...] for p in primes],

using list comprehension notation with \ denoting set subtraction of arithmetic progressions of numbers.

Primes can also be produced by iteratively sieving out the composites through divisibility testing by sequential primes, one prime at a time. It is not the sieve of Eratosthenes but is often confused with it, even though the sieve of Eratosthenes 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.<ref name="ONeill"/>

When testing each prime, the optimal trial division algorithm uses all prime numbers not exceeding its square root, whereas the sieve of Eratosthenes produces each composite from its prime factors only, and gets the primes "for free", between the composites. The widely known 1975 functional sieve code by David Turner<ref>Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975. (<syntaxhighlight lang="haskell" inline>primes = sieve [2..]; sieve (p:nos) = p:sieve (remove (multsof p) nos); remove m = filter (not . m); multsof p n = rem n p==0</syntaxhighlight>). But see also Peter Henderson, Morris, James Jr., A Lazy Evaluator, 1976, where we find the following, attributed to P. Quarendon: <syntaxhighlight lang="python" inline>primeswrt[x;l] = if car[l] mod x=0 then primeswrt[x;cdr[l]] else cons[car[l];primeswrt[x;cdr[l]]] ; primes[l] = cons[car[l];primes[primeswrt[car[l];cdr[l]]]] ; primes[integers[2]]</syntaxhighlight>; the priority is unclear.</ref> is often presented as an example of the sieve of Eratosthenes<ref name="Runciman"/> but is actually a sub-optimal trial division sieve.<ref name="ONeill"/>

Algorithmic complexity

The sieve of Eratosthenes is a popular way to benchmark computer performance.<ref name="peng1985fall">Template:Cite news</ref> The time complexity of calculating all primes below Template:Mvar in the random access machine model is Template:Math operations, a direct consequence of the fact that the prime harmonic series asymptotically approaches Template:Math. It has an exponential time complexity with regard to length of the input, though, which makes it a pseudo-polynomial algorithm. The basic algorithm requires Template:Math of memory.

The bit complexity of the algorithm is Template:Math bit operations with a memory requirement of Template:Math.<ref>Pritchard, Paul, "Linear prime-number sieves: a family tree," Sci. Comput. Programming 9:1 (1987), pp. 17–35.</ref>

The normally implemented page segmented version has the same operational complexity of Template:Math as the non-segmented version but reduces the space requirements to the very minimal size of the segment page plus the memory required to store the base primes less than the square root of the range used to cull composites from successive page segments of size Template:Math.

A special (rarely, if ever, implemented) segmented version of the sieve of Eratosthenes, with basic optimizations, uses Template:Math operations and Template:Math bits of memory.<ref name="Pritchard1">Paul Pritchard, "A sublinear additive sieve for finding prime numbers", Communications of the ACM 24 (1981), 18–23. Template:MR</ref><ref name="Pritchard2">Paul Pritchard, Explaining the wheel sieve, Acta Informatica 17 (1982), 477–485. Template:MR</ref><ref name="Pritchard3">Paul Pritchard, "Fast compact prime number sieves" (among others), Journal of Algorithms 4 (1983), 332–344. Template:MR</ref>

Using big O notation ignores constant factors and offsets that may be very significant for practical ranges: The sieve of Eratosthenes variation known as the Pritchard wheel sieve<ref name="Pritchard1" /><ref name="Pritchard2" /><ref name="Pritchard3" /> has an Template:Math performance, but its basic implementation requires either a "one large array" algorithm which limits its usable range to the amount of available memory else it needs to be page segmented to reduce memory use. When implemented with page segmentation in order to save memory, the basic algorithm still requires about Template:Math bits of memory (much more than the requirement of the basic page segmented sieve of Eratosthenes using Template:Math bits of memory). Pritchard's work reduced the memory requirement at the cost of a large constant factor. Although the resulting wheel sieve has Template:Math performance and an acceptable memory requirement, it is not faster than a reasonably Wheel Factorized basic sieve of Eratosthenes for practical sieving ranges.

Euler's sieve

Euler's proof of the zeta product formula contains a version of the sieve of Eratosthenes in which each composite number is eliminated exactly once.<ref name="intro" /> The same sieve was rediscovered and observed to take linear time by Template:Harvtxt.<ref>Template:Citation.</ref> It, too, starts with a list of numbers from 2 to Template:Mvar in order. On each step the first element is identified as the next prime, is multiplied with each element of the list (thus starting with itself), and the results are marked in the list for subsequent deletion. The initial element and the marked elements are then removed from the working sequence, and the process is repeated:

 [2] (3) 5  7  9  11  13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79  ...
 [3]    (5) 7     11  13    17 19    23 25    29 31    35 37    41 43    47 49    53 55    59 61    65 67    71 73    77 79  ...
 [4]       (7)    11  13    17 19    23       29 31       37    41 43    47 49    53       59 61       67    71 73    77 79  ...
 [5]             (11) 13    17 19    23       29 31       37    41 43    47       53       59 61       67    71 73       79  ...
 [...]

Here the example is shown starting from odds, after the first step of the algorithm. Thus, on the Template:Mvarth step all the remaining multiples of the Template:Mvarth prime are removed from the list, which will thereafter contain only numbers coprime with the first Template:Mvar primes (cf. wheel factorization), so that the list will start with the next prime, and all the numbers in it below the square of its first element will be prime too.

Thus, when generating a bounded sequence of primes, when the next identified prime exceeds the square root of the upper limit, all the remaining numbers in the list are prime.<ref name="intro" /> In the example given above that is achieved on identifying 11 as next prime, giving a list of all primes less than or equal to 80.

Note that numbers that will be discarded by a step are still used while marking the multiples in that step, e.g., for the multiples of 3 it is Template:Nowrap, Template:Nowrap, Template:Nowrap, Template:Nowrap, ..., Template:Nowrap, ..., so care must be taken dealing with this.<ref name="intro" />

References

Template:Reflist

External links

primesieve – Very fast highly optimized C/C++ segmented Sieve of Eratosthenes
Eratosthenes, sieve of at Encyclopaedia of Mathematics
Interactive JavaScript Page
Sieve of Eratosthenes by George Beck, Wolfram Demonstrations Project.
Sieve of Eratosthenes in Haskell
Sieve of Eratosthenes algorithm illustrated and explained. Java and C++ implementations.
A related sieve written in x86 assembly language
Fast optimized highly parallel CUDA segmented Sieve of Eratosthenes in C
SieveOfEratosthenesInManyProgrammingLanguages c2 wiki page
The Art of Prime Sieving Sieve of Eratosthenes in C from 1998 with nice features and algorithmic tricks explained.

Template:Number theoretic algorithms