Edit filter log

'[[File:Sieve of Eratosthenes animation.gif|right|frame|Sieve of Eratosthenes: algorithm steps for primes below 121 (including optimization of starting from prime's square).]] In [[mathematics]], the '''[[Sieve theory|sieve]] of Eratosthenes''' ({{lang-grcnumber of [[Generating primes#Prime sieves|prime number sieve]]s, is a simple, ancient [[algorithm]] for finding all [[prime number]]s up to any given limit. It does so by iteratively marking as [[composite number|composite]] (i.e., not prime) the multiples of each prime, starting with the multiples of 2.<ref name="horsley">Horsley, Rev. Samuel, F. R. S}'' or, The Sieve of Eratosthenes. Being an account of his method The multiples of a given prime are generated as a sequence of numbers starting from that prime, with [[arithmetic progression|constant difference between them]]<!-- "ταυτη διαχωριζομεν" says Nicomachus, p.29, which I take to mean "equally separated"--> that is equal to that prime.<ref name="horsley" /> 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" /> The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes. It is named after [[Eratosthenes|Eratosthenes of Cyrene]], a [[Greek mathematics|Greek mathematician]]; although none of his works have survived, the sieve was described and attributed to Eratosthenes in the ''[[Introduction to Arithmetic]]'' by [[Nicomachus]].<ref>[[Nicomachus]], ''Introduction to Arithmetic'', I, 13. [http://www.archive.org/stream/nicomachigerasen00nicouoft#page/29/mode/1up]</ref> The sieve may be used to find primes in [[arithmetic progression]]s.<ref>J. C. Morehead, "Extension of the Sieve of Eratosthenes to arithmetical progressions and applications", [http://www.jstor.org/stable/1967477 Annals of Mathematics, Second Series '''10''':2 (1909), pp. 88–104].</ref> ==Overview== {{quote box|fontsize = 95%|''Sift the Two's and Sift the Three's,''<br />''The Sieve of Eratosthenes.''<br />''When the multiples sublime,''<br />''The numbers that remain are Prime.''|quoted=1|salign=center|source=Anonymous<ref>Clocksin, William F., Christopher S. Mellish, Programming in Prolog, 1984, p. 170. ISBN 3-540-11046-1.</ref>}} A [[prime number]] is a [[natural number]] that has exactly two distinct natural number [[divisor]]s: [[1 (number)|1]] and itself. To find all the prime numbers less than or equal to a given integer ''n'' by Eratosthenes' method # Create a list of consecutive integers from 2 through ''n'': (2, 3, 4, ..., ''n''). # Initially, let ''p'' equal 2, the smallest prime number. # Enumerate the multiples of ''p'' by counting to ''n'' from ''2p'' in increments of ''p'', and mark them in the list (these will be 2''p'', 3''p'', 4''p'', ... ; the ''p'' itself should not be marked). # Find the first number greater than ''p'' in the list that is not marked. If there was no such number, stop. Otherwise, let ''p'' 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 ''n''. The main idea here is that every value given to ''p'' will be prime, because we have already marked all the multiples of the numbers less than ''p''. Note that some of the numbers being marked may have already been marked earlier (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 ''p''², 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 ''p''² is greater than ''n''.<ref name="horsley" /> <!-- This does not appear in the algorithm as described by Nicomachus.<ref>Nicomachus, ibid., p. 31, where, e.g., 93 is marked as a multiple of 31.</ref> ---- The above is based on wrong reading of the table in Nicomachus p. 31: main factors actually appear in upper row in cells, and their corresponding coefficients in the bottom row; 5 first appears in bottom row for 15 but in top row for 25, and 7 for 49. For 93, 31 is marked in bottom row, below 3. (He also marks 81 as 9*9 and 3*27, so wasn't working with only prime factors, but that's besides the point here.) What the text is saying in Latin or Greek, I have no idea. --> Another refinement is to initially list odd numbers only, (3, 5, ..., ''n''), and count in increments of '''''2'''p'' from ''p''² in step 3, thus marking only odd multiples of ''p''. This actually appears in the original algorithm.<ref name="horsley" /> <!-- <ref>Nicomachus, ibid., p. 31, where only odd numbers appear in the table.</ref> Again, the table is not by Nicomachus; it is in the margins, and in Latin. --> 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 ''p'' are generated that are coprime with those small primes, in the first place.<ref name="Runciman">{{Cite journal | doi = 10.1017/S0956796897002670| title = Functional Pearl: Lazy wheel sieves and spirals of primes| journal = J. Functional Programming| volume = 7| issue = 2| pages = 219–225| year = 1997| last1 = Runciman | first1 = Colin| url = http://eprints.whiterose.ac.uk/3784/1/runcimanc1.pdf}}</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 First number in the list is 2; cross out every 2nd number in the list after it by counting up from 2 in increments of 2 (these will be all the multiples of 2 in the list): 2 3 <s> 4 </s> 5 <s> 6 </s> 7 <s> 8 </s> 9 <s>10</s> 11 <s>12</s> 13 <s>14</s> 15 <s>16</s> 17 <s>18</s> 19 <s>20</s> 21 <s>22</s> 23 <s>24</s> 25 <s>26</s> 27 <s>28</s> 29 <s>30</s> Next number in the list after 2 is 3; cross out every 3rd number in the list after it by counting up from 3 in increments of 3 (these will be all the multiples of 3 in the list): 2 3 <s> 4 </s> 5 <s> 6 </s> 7 <s> 8 </s><s> 9 </s><s> 10</s> 11 <s>12</s> 13 <s>14 </s><s>15 </s><s>16</s> 17 <s>18</s> 19 <s>20 </s><s>21 </s><s>22</s> 23 <s>24</s> 25 <s>26 </s><s>27 </s><s>28</s> 29 <s>30</s> Next number not yet crossed out in the list after 3 is 5; cross out every 5th number in the list after it by counting up from 5 in increments of 5 (i.e. all the multiples of 5): 2 3 <s> 4 </s> 5 <s> 6 </s> 7 <s> 8 </s><s> 9 </s><s> 10</s> 11 <s>12</s> 13 <s>14 </s><s>15 </s><s>16</s> 17 <s>18</s> 19 <s>20 </s><s>21 </s><s>22</s> 23 <s>24 </s><s>25 </s><s>26 </s><s>27 </s><s>28</s> 29 <s>30</s> Next number not yet crossed out in the list after 5 is 7; the next step would be to cross out every 7th number inafter 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 left not crossed out in the list at this point are all the prime numbers below 30: 2 3 5 7 11 13 17 19 23 29 ==Algorithm and variants== The sieve of Eratosthenes can be expressed in [[pseudocode]], as follows:<ref name="sedgewick">{{cite book |last1=Sedgewick |first1=Robert |title=Algorithms in C++ |publisher=Addison-Wesley |year=1992 |isbn=0-201-51059-6 |accessdate=2011-10-26 }}, p. 16.</ref><ref name="intro">[http://research.cs.wisc.edu/techreports/1990/TR909.pdf 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> '''Input''': an integer ''n'' > 1 &nbsp;<!-- these &nbsp; prevent bots messing it up --> '''Let''' ''A'' be an '''array of Boolean''' values, indexed by '''integer'''s 2 to ''n'', initially all '''set''' to '''true'''. &nbsp; '''for''' ''i'' = 2, 3, 4, ..., not exceeding {{math|''{{sqrt|n}}''}}: '''if''' ''A''[''i''] '''is''' '''true''': '''for''' ''j'' = ''i''², ''i''²+''i'', ''i''²+2''i'', ''i''²+3''i'', ..., not exceeding ''n''&thinsp;: ''A''[''j''] := '''false''' &nbsp; '''Output''': all ''i'' such that ''A''[''i''] '''is''' '''true'''. This algorithm produces all primes not greater than {{mvar|n}}. It includes a common optimization, which is to start enumerating the multiples of each prime {{mvar|i}} from {{math|''i''²}}. The time complexity of this algorithm is {{math|O(''n'' log log ''n'')}}.{{r|intro}} ===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.{{r|intro}} For large {{mvar|n}}, the range of primes may not fit in memory; worse, even for moderate {{mvar|n}}, its [[CPU cache|cache]] use is highly suboptimal: the algorithm walks through the entire array {{mvar|A}}, 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:{{r|intro}}<ref>{{Cite journal | last1 = Bays | first1 = Carter | last2 = Hudson | first2 = Richard H. | year = 1977 | title = The segmented sieve of Eratosthenes and primes in arithmetic progressions to 10¹² | journal = BIT | volume = 17 | issue = 2 | pages = 121–127 | publisher = | jstor = | doi = 10.1007/BF01932283 | url = | format = | accessdate = }}</ref> # Divide the range 2 through {{mvar|n}} into segments of some size {{math|Δ ≤ {{sqrt|''n''}}}}. # Find the primes up to {{math|Δ}}, using the "regular" sieve. # For each {{math|Δ}}-sized block from {{math|{{sqrt|''n''}} + 1}} to {{mvar|n}}, set up a Boolean array of size {{math|Δ}}. Eliminate the multiples of each prime {{math|''p'' ≤ {{sqrt|''n''}}}} found in step 2. If {{math|Δ}} is chosen to be {{math|{{sqrt|''n''}}}}, the space complexity of the algorithm is {{math|O({{sqrt|''n''}})}}, while the time complexity is the same as that of the regular sieve.{{r|intro}} For ranges with upper limit {{math|''n''}} so large that the sieving primes below {{math|''{{sqrt|n}}''}} as required by the page segmented sieve of Eratosthenes cannot fit in memory, a slower but much more space-efficient sieve like that [[sieve of Sorenson]] can be used instead.<ref>J. Sorenson, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.1737 The pseudosquares prime sieve], Proceedings of the 7th International Symposium on Algorithmic Number Theory. (ANTS-VII, 2006).</ref> ===Incremental sieve=== [[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 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 [[Analysis of algorithms|complexity]] than that of the sieve of Eratosthenes in generating ranges of primes.<ref name="ONeill"/> 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 programming|functional]] code by [[David Turner (computer scientist)|David Turner]]<ref>Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975. (<source lang="haskell" inline>sieve (p:xs) = p : sieve [x | x <- xs, rem x p > 0]; primes = sieve [2..]</source>)</ref> is often presented as an example of the sieve of Eratosthenes<ref name="Runciman"/> but is actually a sub-optimal trial division algorithm.<ref name="ONeill"/> An incremental formulation of the sieve<ref name="ONeill">O'Neill, Melissa E., [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf "The Genuine Sieve of Eratosthenes"], Journal of Functional Programming, Published online by Cambridge University Press 9 October 2008 {{doi|10.1017/S0956796808007004}}, 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 ''p'' are generated directly, by counting up from the square of the prime in increments of ''p'' (or 2''p'' for odd primes). The generation must be initiated only when the prime's square is reached, to avoid adverse effects on efficiency. ==Computational analysis== {{refimprove section|date=June 2015}} The work performed by this algorithm is almost entirely the operations to cull the composite number representations which for the basic non-optimized version is the sum of the range divided by each of the primes up to that range or <math>n\sum_{p\le n}\frac1p</math>, where n is the sieving range in this and all further analysis. By rearranging [[Mertens' theorems|Mertens' 2nd theorem]], this is equal to <math>n\ln\ln n+M</math> as n approaches infinity, where M is the [[Meissel–Mertens constant]] of about 0.2614972128476427837554268386086958590516... The optimization of starting at the square of each prime and only culling for primes less than the square root changes the "{{math|''n''}}" in the above expression to {{sqrt|''n''}} (or {{math|''n''^{{{sfrac|1|2}}}}}) and not culling until the square means that the sum of the base primes each minus two is subtracted from the operations. As the sum of the first {{math|''x''}} primes is <math>\frac1{2}x^2\ln x</math><ref>E. Bach and J. Shallit, §2.7 in Algorithmic Number Theory, Vol. 1: Efficient Algorithms, MIT Press, Cambridge, MA, 1996.</ref> and the [[Prime number theorem]] says that {{math|''x''}} is approximately <math>\frac{x}{\ln x}</math> then the sum of primes to {{math|''n''}} is <math>\frac12\frac{n^2}{\ln n}</math> and therefore the sum of base primes to {{sqrt|''n''}} is <math>\frac1{\ln n}</math> expressed as a factor of {{math|''n''}}. The extra offset of two per base prime is <math>2\pi(n^\frac12)</math> where <math>\pi</math> is the [[Prime-counting function]] in this case or <math>\frac{4 n^\frac12}{\ln n}</math>; expressing this as a factor of {{math|''n''}} as are the other terms, this is <math>\frac{4}{\sqrt n\ln n}</math>. Combining all of this, the expression for the number of optimized operations without wheel factorization is <math>\ln\ln n-\frac1{\ln n}\left(1-\frac{4}{\sqrt{n}}\right)+M-\ln 2</math>. For the wheel factorization cases, there is a further offset of the operations not done of <math>\sum_{p\le x}\frac1p</math> where {{math|''x''}} is the highest wheel prime and a constant factor of the whole expression is applied which is the fraction of remaining prime candidates as compared to the repeating wheel circumference. The wheel circumference is <math>\prod_{p\le x}p</math> and it can easily be determined that this wheel factor is <math>\prod_{p\le x}\frac{p-1}{p}</math> as <math>\frac{p-1}{p}</math> is the fraction of remaining candidates for the highest wheel prime, {{math|''x''}}, and each succeeding smaller prime leaves its corresponding fraction of the previous combined fraction. Combining all of the above analysis, the total number of operations for a sieving range up to {{math|''n''}} including wheel factorization for primes up to {{math|''x''}} is approximately: <math>\prod_{p\le x}\frac{p-1}{p}\left(\ln\ln n-\frac1{\ln n}\left(1-\frac{4}{\sqrt{n}}\right)+M-\ln 2-\sum_{p\le x}\frac1p\right)</math> To show that the above expression is a good approximation to the number of composite number cull operations performed by the algorithm, following is a table showing the actually measured number of operations for a practical implementation of the sieve of Eratosthenes as compared to the number of operations predicted from the above expression with both expressed as a fraction of the range (rounded to four decimal places) for different sieve ranges and wheel factorizations (Note that the last column is a maximum practical wheel as to the size of the wheel gaps Look Up Table - almost 10 million values): :{| class="wikitable" style="text-align: center" ! ''n'' ! colspan=2| no wheel ! colspan=2| odds ! colspan=2| 2/3/5 wheel ! colspan=2| 2/3/5/7 wheel ! colspan=2| 2/3/5/7/11/13/17/19 wheel |- | ''10³'' | 1.4090 || 1.3745 | 0.4510 || 0.4372 | 0.1000 || 0.0909 | 0.0580 || 0.0453 | 0.0060 || ------ |- | ''10⁴'' | 1.6962 || 1.6844 | 0.5972 || 0.5922 | 0.1764 || 0.1736 | 0.1176 || 0.1161 | 0.0473 || 0.0391 |- | ''10⁵'' | 1.9299 || 1.9261 | 0.7148 || 0.7130 | 0.2388 || 0.2381 | 0.1719 || 0.1714 | 0.0799 || 0.0805 |- | ''10⁶'' | 2.1218 || 2.1220 | 0.8109 || 0.8110 | 0.2902 || 0.2903 | 0.2161 || 0.2162 | 0.1134 || 0.1140 |- | ''10⁷'' | 2.2850 || 2.2863 | 0.8925 || 0.8932 | 0.3337 || 0.3341 | 0.2534 || 0.2538 | 0.1419 || 0.1421 |- | ''10⁸'' | 2.4257 || 2.4276 | 0.9628 || 0.9638 | 0.3713 || 0.3718 | 0.2856 || 0.2860 | 0.1660 || 0.1662 |} The above table shows that the above expression is a very good approximation to the total number of culling operations for sieve ranges of about a hundred thousand (10⁵) and above. ==Algorithmic complexity== The sieve of Eratosthenes is a popular way to benchmark computer performance.<ref name="peng1985fall">{{cite news | url=https://archive.org/stream/byte-magazine-1985-11/1985_11_BYTE_10-11_Inside_the_IBM_PCs#page/n245/mode/2up | title=One Million Primes Through the Sieve | work=BYTE | date=Fall 1985 | accessdate=19 March 2016 | author=Peng, T. A. | pages=243-244}}</ref> As can be seen from the above by removing all constant offsets and constant factors and ignoring terms that tend to zero as n approaches infinity, the time complexity of calculating all primes below ''n'' in the [[random access machine]] model is <math>O(n \log\log n)</math> operations, a direct consequence of the fact that the [[prime harmonic series]] asymptotically approaches <math>\log \log n</math>. It has an exponential time complexity with regard to input size, though, which makes it a [[Pseudo-polynomial time|pseudo-polynomial]] algorithm. The basic algorithm requires <math>O(n)</math> of memory. The [[bit complexity]] of the algorithm is <math>O(n (\log n) (\log \log n))</math> bit operations with a memory requirement of <math>O(n)</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 <math>O(n \log\log n)</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 <math>O(\frac{\sqrt{n}}{\log n})</math>. A special rarely if ever implemented segmented version of the sieve of Eratosthenes, with basic optimizations, uses <math>O(n)</math> operations and <math>O(n^{1/2}\log\log n/\log n)</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. MR 82c:10011</ref><ref name="Pritchard2">Paul Pritchard, Explaining the wheel sieve, Acta Informatica 17 (1982), 477–485. MR 84g:10015</ref><ref name="Pritchard3"> Paul Pritchard, Fast compact prime number sieves (among others), Journal of Algorithms 4 (1983), 332–344. MR 85h:11080</ref> To show that the above approximation in complexity is not very accurate even for about as large as practical a range, the following is a table of the estimated number of operations as a fraction of the range rounded to four places, the calculated ratio for a factor of ten change in range based on this estimate, and the factor based on the ''log log n'' estimate for various ranges and wheel factorizations (the combo column uses a frequently practically used pre-cull by the maximum wheel factorization but only the 2/3/5/7 wheel for the wheel factor as the full factorization is difficult to implement efficiently for page segmentation): :{| class="wikitable" ! ''n'' ! colspan=3 | no wheel ! colspan=3 | odds ! colspan=3 | 2/3/5 wheel ! colspan=3 | 2/3/5/7 wheel ! colspan=3 | combo wheel ! colspan=3 | 2/3/5/7/11/13/17/19 wheel |- | 10⁶ | 2.122 || 1.102 || 1.075 | 0.811 || 1.137 || 1.075 | 0.2903 || 1.22 || 1.075 | 0.2162 || 1.261 || 1.075 | 0.1524 || 1.416 || 1.075 | 0.114 || 1.416 || 1.075 |- | 10⁷ | 2.2863 || 1.077 || 1.059 | 0.8932 || 1.101 || 1.059 | 0.3341 || 1.151 || 1.059 | 0.2537 || 1.174 || 1.059 | 0.1899 || 1.246 || 1.059 | 0.1421 || 1.246 || 1.059 |- | 10⁸ | 2.4276 || 1.062 || 1.048 | 0.9638 || 1.079 || 1.048 | 0.3718 || 1.113 || 1.048 | 0.286 || 1.127 || 1.048 | 0.2222 || 1.17 || 1.048 | 0.1662 || 1.17 || 1.048 |- | 10⁹ | 2.5514 || 1.051 || 1.04 | 1.0257 || 1.064 || 1.04 | 0.4048 || 1.089 || 1.04 | 0.3143 || 1.099 || 1.04 | 0.2505 || 1.127 || 1.04 | 0.1874 || 1.127 || 1.04 |- | 10¹⁰ | 2.6615 || 1.043 || 1.035 | 1.0808 || 1.054 || 1.035 | 0.4342 || 1.073 || 1.035 | 0.3395 || 1.08 || 1.035 | 0.2757 || 1.101 || 1.035 | 0.2063 || 1.101 || 1.035 |- | 10¹¹ | 2.7608 || 1.037 || 1.03 | 1.1304 || 1.046 || 1.03 | 0.4607 || 1.061 || 1.03 | 0.3622 || 1.067 || 1.03 | 0.2984 || 1.082 || 1.03 | 0.2232 || 1.082 || 1.03 |- | 10¹² | 2.8511 || 1.033 || 1.027 | 1.1755 || 1.04 || 1.027 | 0.4847 || 1.052 || 1.027 | 0.3828 || 1.057 || 1.027 | 0.319 || 1.069 || 1.027 | 0.2387 || 1.069 || 1.027 |- | 10¹³ | 2.9339 || 1.029 || 1.024 | 1.217 || 1.035 || 1.024 | 0.5068 || 1.046 || 1.024 | 0.4018 || 1.049 || 1.024 | 0.3379 || 1.059 || 1.024 | 0.2528 || 1.059 || 1.024 |- | 10¹⁴ | 3.0104 || 1.026 || 1.022 | 1.2552 || 1.031 || 1.022 | 0.5272 || 1.04 || 1.022 | 0.4193 || 1.044 || 1.022 | 0.3554 || 1.052 || 1.022 | 0.2659 || 1.052 || 1.022 |- | 10¹⁵ | 3.0815 || 1.024 || 1.02 | 1.2907 || 1.028 || 1.02 | 0.5462 || 1.036 || 1.02 | 0.4355 || 1.039 || 1.02 | 0.3717 || 1.046 || 1.02 | 0.2781 || 1.046 || 1.02 |- | 10¹⁶ | 3.1478 || 1.022 || 1.018 | 1.3239 || 1.026 || 1.018 | 0.5639 || 1.032 || 1.018 | 0.4507 || 1.035 || 1.018 | 0.3868 || 1.041 || 1.018 | 0.2894 || 1.041 || 1.018 |} The above shows that the ''log log n'' estimate is not very accurate even for maximum practical ranges of about 10¹⁶. One can see why it does not match by looking at the computational analysis above and seeing that within these practical sieving range limits, there are very significant constant offset terms such that the very slowly growing ''log log n'' term does not get large enough so as to make these terms insignificant until the sieving range approaches infinity - well beyond any practical sieving range. Within these practical ranges, these significant constant offsets mean that the performance of the Sieve of Eratosthenes is much better than one would expect just using the asymptotic time complexity estimates by a significant amount, but that also means that the slope of the performance with increasing range is steeper than predicted as the benefit of the constant offsets becomes slightly less significant. One should also note that in using the calculated operation ratios to the sieve range, it must be less than about 0.2587 in order to be faster than the often compared [[sieve of Atkin]] '''if the operations take approximately the same time each in CPU clock cycles''', which is a reasonable assumption for the one huge bit array algorithm. Using that assumption, the sieve of Atkin is only faster than the maximally wheel factorized sieve of Eratosthenes for ranges of over 10¹³ at which point the huge sieve buffer array would need about a quarter Terabyte (about 250 Gigabytes) of RAM memory even if bit packing were used - i.e., not very practical! An analysis of the page segmented versions will show that the assumption that the time per operation stays the same between the two algorithms does not hold for page segmentation and that the sieve of Atkin operations get slower much faster than the sieve of Eratosthenes with increasing range. Thus for practical purposes, the maximally wheel factorized Sieve of Eratosthenes is faster than the Sieve of Atkin although the Sieve of Atkin is faster for lesser amounts of wheel factorization. Using [[Big O Notation]] is also not the correct way to compare practical performance of even variations of the Sieve of Eratosthenes as it 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 O(n) 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 <math>O\left(\frac{n}{\log n}\right)</math> bits of memory (much more than the requirement of the basic page segmented Sieve of Eratosthenes using <math>O\left(\frac{\sqrt{n}}{\log n}\right)</math> bits of memory). Pritchard's work reduced the memory requirement to the limit as described above the table, but the cost is a fairly large constant factor of about three in execution time to about 0.75 times the sieve range due to the complex computations required to do so. As can be seen from the above table for the basic Sieve of Eratosthenes, even though the resulting wheel sieve has O(n) performance and an acceptable memory requirement, it will never be faster than a reasonably Wheel Factorized basic Sieve of Eratosthenes for any practical sieving range by a factor of about two. Other than that it is quite complex to implement, it is rarely practically implemented because it still uses more memory than the basic Sieve of Eratosthenes implementations described here as well as being slower for practical ranges. It is thus more of an intellectual curiosity than something practical. ==Euler's Sieve== Euler's [[Proof of the Euler product formula for the Riemann zeta function#Proof of the Euler product formula|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 {{harvtxt|Gries|Misra|1978}}.<ref>{{citation | last1 = Gries | first1 = David | author1-link = David Gries | last2 = Misra | first2 = Jayadev | date = December 1978 | doi = 10.1145/359657.359660 | issue = 12 | journal = [[Communications of the ACM]] | pages = 999–1003 | title = A linear sieve algorithm for finding prime numbers | volume = 21}}.</ref> It, too, starts with a [[list (computing)|list]] of numbers from ''2'' to ''n'' in order. On each step the first element is identified as the next prime and the results of multiplying this prime with each element of the list 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: <small> [2] (3) 5 7 <u>9</u> 11 13 <u>15</u> 17 19 <u>21</u> 23 25 <u>27</u> 29 31 <u>33</u> 35 37 <u>39</u> 41 43 <u>45</u> 47 49 <u>51</u> 53 55 <u>57</u> 59 61 <u>63</u> 65 67 <u>69</u> 71 73 <u>75</u> 77 79 ... [3] (5) 7 11 13 17 19 23 <u>25</u> 29 31 <u>35</u> 37 41 43 47 49 53 <u>55</u> 59 61 <u>65</u> 67 71 73 77 79 ... [4] (7) 11 13 17 19 23 29 31 37 41 43 47 <u>49</u> 53 59 61 67 71 73 <u>77</u> 79 ... [5] (11) 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 ... [...]</small> Here the example is shown starting from odds, after the first step of the algorithm. Thus, on the ''k''th step all the remaining multiples of the ''k''th prime are removed from the list, which will thereafter contain only numbers coprime with the first ''k'' 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 {{math|1=3 · 3 = 9}}, {{math|1=3 · 5 = 15}}, {{math|1=3 · 7 = 21}}, {{math|1=3 · '''''9''''' = 27}}, ..., {{math|1=3 · '''''15''''' = 45}}, ..., so care must be taken dealing with this.<ref name="intro" /> ==See also== * [[Sieve of Sundaram]] * [[Sieve of Atkin]] * [[Sieve theory]] ==References== {{Reflist|2}} ==External links== * [http://www.encyclopediaofmath.org/index.php/Eratosthenes,_sieve_of ''Eratosthenes, sieve of'' at Encyclopaedia of Mathematics] * [http://www.hbmeyer.de/eratosiv.htm Interactive JavaScript Page] * [http://demonstrations.wolfram.com/SieveOfEratosthenes/ Sieve of Eratosthenes] by George Beck, [[Wolfram Demonstrations Project]]. * [https://wiki.haskell.org/Prime_numbers#Sieve_of_Eratosthenes Sieve of Eratosthenes in Haskell] * [http://www.algolist.net/Algorithms/Number_theoretic_algorithms/Sieve_of_Eratosthenes Sieve of Eratosthenes algorithm illustrated and explained. Java and C++ implementations.] * [http://zsmith.co/primes.html A related sieve written in x86 assembly language] * [http://sites.google.com/site/bbuhrow/ A highly optimized Sieve of Eratosthenes in C] * [http://paratechnical.blogspot.com/2011/01/c-implementation-of-parallel-sieve-of.html A parallel implementation in C#] * [http://c2.com/cgi/wiki?SieveOfEratosthenesInManyProgrammingLanguages SieveOfEratosthenesInManyProgrammingLanguages c2 wiki page] * [http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html The Art of Prime Sieving] Sieve of Eratosthenes in C from 1998 with nice features and algorithmic tricks explained. <!--spacing--> {{number theoretic algorithms}} {{DEFAULTSORT:Sieve Of Eratosthenes}} [[Category:Primality tests]] [[Category:Articles with example pseudocode]] [[Category:Sieve theory| ]] [[Category:Algorithms]]'