Editing Sieve of Eratosthenes (section)

==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| hdl = 1813/6407 | s2cid = 11990373 | url = https://ecommons.cornell.edu/bitstream/1813/6407/1/77-313.pdf
 | hdl-access = free
 }}.</ref> It, too, starts with a [[list (computing)|list]] of numbers from 2 to {{mvar|n}} 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:
<div style="font-size:85%;">  <!-- these &nbsp;s are put here hoping to prevent bots messing it up -->
 &nbsp;[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  ...
 &nbsp;[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  ...
 &nbsp;[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  ...
 &nbsp;[5]             (11) 13    17 19    23       29 31       37    41 43    47       53       59 61       67    71 73       79  ...
 &nbsp;[...]
</div>

Here the example is shown starting from odds, after the first step of the algorithm. Thus, on the {{mvar|k}}th step all the remaining multiples of the {{mvar|k}}th prime are removed from the list, which will thereafter contain only numbers coprime with the first {{mvar|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 {{nowrap|1=3 × 3 = 9}}, {{nowrap|1=3 × 5 = 15}}, {{nowrap|1=3 × 7 = 21}}, {{nowrap|1=3 × '''''9''''' = 27}}, ..., {{nowrap|1=3 × '''''15''''' = 45}}, ..., so care must be taken dealing with this.<ref name="intro" />