Prerequisite:
In this article we’ll explain what a sieve is, based on the most famous example, the sieve of Eratosthenes. It allows you to answer a simple question: given an integer N \geq 2, what are the prime numbers less than or equal to N?
From a property of divisors to the sieve of Eratosthenes
To find prime numbers less than or equal to N, it is sufficient to have a criterion to establish whether a number is prime or not: in fact, it would be sufficient to apply this criterion to all integers between 2 and N and gradually mark which ones are prime.
There are several criteria for establishing whether a number is prime, all of which become more and more laborious as the number under consideration increases, but the simplest and most famous one is the following Property:
Properties of divisors less than or equal to the square root
If a natural number N greater than 1 is not divisible by any prime number less than or equal to \sqrt{N}, then N is prime.
To better understand this Property, let’s consider the equivalent statement obtained by inverting the implication:
Properties of divisors less than or equal to the square root, equivalent form
If a natural number N greater than 1 is not prime, then it has (at least) a prime divisor less than or equal to \sqrt{N}.
The proof is very simple, but important. Let’s consider a number N greater than 1 not prime and suppose by contradiction that it has no prime divisors less than or equal to \sqrt{N}. Then N, not being prime, must have at least two prime divisors p and q. But, by our assumption, both of these divisors are greater than \sqrt{N}, so N \geq pq \gt \sqrt{N} \sqrt{N} = N, hence the absurd N \gt N. So the initial assumption must be false, i.e. N must have at least one prime divisor less than or equal to \sqrt{N}.
Property C.1 allows us to establish if a number is prime, but at the same time it assumes that we already know some prime numbers. Isn’t that a contradiction?
Property C.1 indeed allows us to establish whether a number is prime assuming we already know which prime numbers are less than or equal to its square root. So the objection is legitimate, because ideally a criterion for establishing whether a number is prime should not use the concept of prime number, but different concepts already known in other ways.
Actually this is a false problem, for two reasons:
- To determine if a number is prime we could also try dividing N not only by the primes less than or equal to \sqrt{N}, but by all integers greater than 1 and less than or equal to \sqrt{N}. This way of proceeding would not assume any previous knowledge of prime numbers and would guarantee to obtain the same result. Indeed, if a number is not divisible by any integer greater than 1 and less than or equal to \sqrt{N}, a fortiori it is not divisible by any prime in the same interval; conversely, if a number is divisible by some integer k greater than 1 and less than or equal to \sqrt{N}, it is also divisible by some prime in the same interval (in particular, a prime factor of k). Obviously the disadvantage of this method is that it considerably increases the number of divisions necessary to determine if a number is prime.
- Prime numbers can be constructed from one another, starting only from the first of them, i.e. 2. In fact, since 2 is the only prime number less than or equal to 2, on the basis of Property C.1, if \sqrt{N} \leq 2, i.e. N \leq 4, we can determine if N is prime by dividing it only by 2. We could thus determine, without knowing the list of prime numbers a priori, that 3 is prime and 4 is not. At this point we could reapply Property C.1 using the knowledge of the set of prime numbers less than or equal to 4 that we have found, i.e. \{2, 3\}. So if \sqrt{N} \leq 4, i.e. if N \leq 16, according to Property C.1, to determine if N is prime, we just have to try dividing it by 2 and by 3. This way we could build the set of all prime numbers up to 16, which is \{2 , 3, 5, 7, 11, 13\}. Based on this, if \sqrt{N} \leq 16, i.e. if N \leq 256, to check if N is prime it is enough to try dividing it by 2, 3, 5, 7, 11 and 13… and so on.
In short, starting from the knowledge of a single prime number (2), the following ones can be built gradually, using each time as a basis those primes already built in the previous steps. The algorithm that we’ll see shortly, based on Property C.1, applies a mechanism of this kind: the prime numbers less than or equal to the square root of N are constructed gradually, without assuming that they are already known from the beginning.
Now suppose we have set a starting number N and we want to find all prime numbers smaller than it. We could consider all the integers starting from 2 up to N one at a time, applying Property C.1 to each of them, i.e. trying to divide each number by all primes less than or equal to its square root. That is, we could apply the following algorithm:
- Set P : = \{\}
- For any integer n between 2 and N:
- Set p : = 2 and d := 1
- If p \leq \sqrt{n} and d = 1:
- If n is divisible by p, set d : = p
- Otherwise, set p : = \textrm{next element of }P
- Go back to step b.
- If d = 1, add p to the set P
- Return P
If N = 32, the previous algorithm performs the following steps:
- 1. P : = \{\}
- 2. n : = 2
- a. p : = 2, d := 1
- b. The condition “2 \leq \sqrt{2} and 1 = 1” is false
- c. The condition “1 = 1” is true
- P = \{2\}
- 2. n : = 3
- a. p : = 2, d := 1
- b. The condition “2 \leq \sqrt{3} and 1 = 1” is false
- c. The condition “1 = 1” is true
- P = \{2, 3\}
- 2. n : = 4
- a. p : = 2, d := 1
- b. The condition “2 \leq \sqrt{4} and 1 = 1” is true
- i. The condition “4 is divisible by 2” is true
- d : = 2
- b. The condition “2 \leq \sqrt{4} and 2 = 1” is false
- c. The condition “2 = 1” is false
- 2. n : = 5
- a. p : = 2, d := 1
- b. The condition “2 \leq \sqrt{5} and 1 = 1” is true
- ii. The condition “5 is divisible by 2” is false
- p : = 3
- b. The condition “3 \leq \sqrt{5} and 1 = 1” is false
- c. The condition “1 = 1” is true
- P = \{2, 3, 5\}
- 2. n : = 6
- a. p : = 2, d := 1
- b. The condition “2 \leq \sqrt{6} and 1 = 1” is true
- i. The condition “6 is divisible by 2” is true
- d : = 2
- b. The condition “2 \leq \sqrt{6} and 2 = 1” is false
- c. The condition “2 = 1” is false
- 2. n : = 7
- a. p : = 2, d := 1
- b. The condition “2 \leq \sqrt{7} and 1 = 1” is true
- ii. The condition “7 is divisible by 2” is false
- p : = 3
- b. The condition “3 \leq \sqrt{7} and 1 = 1” is false
- c. The condition “1 = 1” is true
- P = \{2, 3, 5, 7\}
- 2. n : = 8
- a. p : = 2, d := 1
- b. The condition “2 \leq \sqrt{8} and 1 = 1” is true
- i. The condition “8 is divisible by 2” is true
- d : = 2
- b. The condition “2 \leq \sqrt{8} and 2 = 1” is false
- c. The condition “2 = 1” is false
- 2. n : = 9
- a. p : = 2, d := 1
- b. The condition “2 \leq \sqrt{9} and 1 = 1” is true
- ii. The condition “9 is divisible by 2” is false
- p : = 3
- b. The condition “3 \leq \sqrt{9} and 1 = 1” is true
- i. The condition “9 is divisible by 3” is true
- d : = 3
- b. The condition “3 \leq \sqrt{9} and 3 = 1” is false
- c. The condition “3 = 1” is false
- 2. n : = 10
- a. p : = 2, d := 1
- b. The condition “2 \leq \sqrt{10} and 1 = 1” is true
- i. The condition “10 is divisible by 2” is true
- d : = 2
- b. The condition “2 \leq \sqrt{10} and 2 = 1” is false
- c. The condition “2 = 1” is false
- 2. n : = 11
- a. p : = 2, d := 1
- b. The condition “2 \leq \sqrt{11} and 1 = 1” is true
- ii. The condition “11 is divisible by 2” is false
- p : = 3
- b. The condition “3 \leq \sqrt{11} and 1 = 1” is true
- ii. The condition “11 is divisible by 3” is false
- p : = 5
- b. The condition “5 \leq \sqrt{11} and 1 = 1” is false
- c. The condition “1 = 1” is true
- P = \{2, 3, 5, 7, 11\}
- …
- 2. n : = 32
- a. p : = 2, d := 1
- b. The condition “2 \leq \sqrt{32} and 1 = 1” is true
- i. The condition “32 is divisible by 2” is true
- d : = 2
- b. The condition “2 \leq \sqrt{32} and 2 = 1” is false
- c. The condition “2 = 1” is false
- Returns \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31\}
We can visualize the behaviour of the algorithm through a table, having as rows the prime numbers less than or equal to \sqrt{N} and as columns the numbers between 2 and N (that is, the n of the algorithm). For example, if N = 32 we’ll have the following table:
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 | 31 | 32 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
2 | |||||||||||||||||||||||||||||||
3 | |||||||||||||||||||||||||||||||
5 |
For the algorithm it is not necessary to know in advance which prime numbers are less than or equal to the square root of N, because they are gradually added to the set P, but to immediately draw the table complete with all the rows we assumed we already knew them.
We can imagine that the algorithm reads the table column by column, from left to right. For each column, it tests whether the column number is divisible by the number in each row, as long as the row number is less than or equal to the square root of the column number. As soon as it finds a row number that divides the column number, or when there are no more rows to examine, it moves to the next column.
If we color the cells corresponding to the division tests carried out in gray and put a dash in the cases in which there is divisibility, we’ll obtain the following representation:
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 | 31 | 32 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
2 | – | – | – | – | – | – | – | – | – | – | – | – | – | – | – | ||||||||||||||||
3 | – | – | – | – | |||||||||||||||||||||||||||
5 | – |
We have obtained a table in which, if the number of a column is not prime, the column contains a dash on the row corresponding to the smallest prime factor of the number; otherwise, if the column number is prime, it contains no dashes.
It should be noted that gray cells rarely cover the entire column. This happens because the division tests stop at the largest prime less than or equal to the square root of the column number (as in the case of 23, which has a square root less than 5, so the last tested prime is 3), moreover, when a divisor is found, we stop in any case, even if there would be other prime numbers to test (as in the case of 27: since its square root is greater than 5, we should also test the divisibility by 5, but we stop at 3 because it is already a divisor).
The idea of the sieve of Eratosthenes consists in reversing the reading order of the table, i.e. reading it by rows, instead of by columns. In practice, prime numbers are considered one at a time, starting from 2 which is the only one supposed to be known from the beginning, and gradually building up the others; for each of them we mark the columns the numbers of which are multiples of the considered prime number and greater than it; by doing so, only the columns the number of which is prime will be left unsigned in the end. The algorithm is as follows:
- Set A : = \{2, 3, 4, \ldots, N\}
- Set p : = 2
- If p \leq \sqrt{N}:
- For any integer n \in A greater than p:
- If n is divisible by p, delete n from A
- Put p : = \textrm{next element of }A
- Go back to step 3.
- For any integer n \in A greater than p:
- Return A
This algorithm may look very different from the previous one, but it actually generates exactly the same table. Indeed, if for example N = 32:
- Initially p = 2, so the algorithm checks, for each element of A = \{2, \ldots, N\}, whether it is divisible by 2 and greater than 2: if so, remove it from the set A. Representing the row of 2, coloring in gray the cells corresponding to the division tests carried out (i.e. one for each element of A) and placing a dash in the cells the column number of which is divisible by 2 and greater than 2 (conditions a. and i. of the algorithm), we’ll obtain:
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 31 32 2 – – – – – – – – – – – – – – – The row of this table is practically identical to the first row of the previous table: the only difference is that now two more division tests have been done, but the dashes are the same.
Now the set A will be reduced to only the numbers of the columns that do not contain a dash, i.e. \{2, 3, 5, 7, 9, 11, 13, 15 , 17 , 19, 21, 23, 25, 27, 29, 31\}. - The algorithm continues by setting p : = 3 and scanning the elements of the new set A greater than 3, therefore only the columns from 4 onwards that don’t have a dash yet. By creating the row of 3, coloring the cells of these columns in gray and again marking the divisibilities with dashes, we’ll obtain:
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 31 32 2 – – – – – – – – – – – – – – – 3 – – – – This line is also practically identical to the corresponding one in the previous table, except for a few more divisibility tests.
At this point the numbers such that the corresponding columns have a dash on the new line will also have been eliminated from the set A, i.e. 9, 15, 21 and 27, so the set will become \{2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31\}. - Finally, the algorithm puts p : = 5 (the last element of A less than or equal to the square root of 32) and iterates the elements of the set A greater than 5, i.e. 7, 11, 13, 17, 19, 23, 25, 29 and 31. On the row of 5, cells with these column numbers will be grayed out and those that are divisible by 5 will contain a dash:
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 31 32 2 – – – – – – – – – – – – – – – 3 – – – – 5 – The last line also coincides with the corresponding one in the previous table, except for a few more divisibility tests.
Now the set A becomes \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31\}. The next element of A is 7, but it is greater than \sqrt{32}, so step 3 of the algorithm ends and, in step 4, the algorithm returns the set A, which now is indeed the set of prime numbers less than or equal to 32. They correspond, like before, to the numbers of the columns without dashes.
We observed that the sieve of Eratosthenes, compared to the previous algorithm, performs more divisibility tests (not necessary, since the result does not change). It’s possible to optimize the algorithm by eliminating these divisibility tests, by changing the criterion “For every integer n \in A greater than p” to “For every integer n \ in A greater than or equal to p^2“. The table obtained by the such modified sieve would be exactly the same as the one obtained by the previous algorithm.
The formal definition of sieve
In the previous section we saw the sieve of Eratosthenes, which is the most famous example of a sieve. But what exactly is a sieve, in general terms?
Now, knowing Eratosthenes’ sieve, you might think that a sieve is an algorithm, similar to the ones we saw in the previous section. Indeed, historically this has been the case. The very name sieve represents a tool formed by a frame with perforated plates which allows only objects of a certain size to pass through:
Using this metaphor in mathematics, we can say that a sieve is a test of divisibility for a specific set of prime numbers, where the inserted objects, i.e. the input data, are the elements of a certain starting set (the one that in the previous section we indicated with A): those divisible by one of the selected prime numbers remain blocked, while the others go further, i.e. they are returned in output.
This image, however useful it may be on an intuitive level, actually has little to do with the sieve theory, i.e. the mathematical theory that studies these tools. In fact, it does not have an algorithmic setting, but a numerical one. From a mathematical point of view a sieve is not defined as an algorithm, because what matters is the final result, which does not depend on the algorithm used. In sieve theory, a sieve is understood as a function, called sieve function, which, starting from a set of natural numbers and some parameters, gives the desired result:
Sieve function
Let A be a finite set of natural numbers, \mathcal{P} a set of prime numbers and z \gt 1 a real number. We define sieve function as the following function, defined for each A, \mathcal{P} and z:
The set A, the set \mathcal{P} and the number z are respectively called sieving set, sieving range and sieving level.
Even if the definition does not indicate which prime numbers the set \mathcal{P} should contain, it is almost always the set of all prime numbers, usually denoted by the symbol \mathbb{P}. In this case, calculating the sieve function means answering the question: “How many elements of A are not divisible by any prime number smaller than z?”. Number theorists try to answer this question in an approximate way, by limiting the sieve function above or below.
If \mathcal{P} does not contain all prime numbers less than z (e.g. \mathcal{P} = \{2, 3, 7\}, without the 5, with z = 8), the question becomes slightly more complex, because in this case we are looking for the elements of A which are not divisible by any prime number less than z limited to the prime numbers in the set \mathcal{P}. For didactic reasons, the definition of sieve function has been stated in these more general terms, as it is found in many texts, but from now on we will always assume that \mathcal{P} = \mathbb{P}, since the difficulty of the problem does not change compared to the more general case.
As expressed in Definition C.1, a sieve function is not easy to compute; we can improve this aspect by writing it in a purely algebraic form. In fact, the following Property is valid:
Sieve function with \mathcal{P} = \mathbb{P}, purely algebraic expression
Let A be a finite set of natural numbers, z \gt 1 a real number, and P(z) the product of the prime numbers less than z. Then:
It’s easy to prove that this writing is equivalent to the definition seen above, but this proof is important to clarify the notation. Formula (1) basically says to add a “1” every time both the following conditions are met:
- a \in A
- \mathrm{GCD}(a, P(z)) = 1
That is, we have to add a “1” for each element of A coprime with P(z). But P(z) is the product of prime numbers less than z; thus, if a number is coprime with P(z), then it cannot be divisible by any prime number less than z. Then the elements satisfying the conditions a \in A and \mathrm{GCD}(a, P(z)) = 1 are precisely those of the set \{a \in A \mid a \textrm{ is not divisible by any element of }\mathbb{P}\textrm{ less than }z \}. Formula (1) tells us that we must count 1 for each of these elements and add up all, so in the end we’ll get the count of the elements themselves, i.e. S( A, \mathbb{P}, z), according to Definition C.1.
Property C.2 seems to suggest an algorithm for the computation of S( A, \mathbb{P}, z), which consists in taking the elements of A one at a time and check if in their factorization there is no prime number less than z, counting 1 if so. However, this is only one possible way, the most immediate, to calculate a sieve function; in the next articles we’ll see other more sophisticated ones.
The sieve of Eratosthenes as a sieve function
In this article we started by introducing the sieve of Eratosthenes from an algorithmic point of view, but then we saw that in general a sieve can be understood as a function, which expresses the concept of sieve on a numerical/set level. Then also the sieve of Eratosthenes, being precisely a sieve, should be expressible as a function, as well as an algorithm. In reality, this is not true, if we want to be rigorous. The original sieve of Eratosthenes (the one we illustrated in the previous paragraph) cannot be expressed as a sieve function; if we want to express it that way, we have to modify it slightly. Let’s see why.
Let’s go back to the example of N = 32. The sieve of Eratosthenes, starting from the set A : = \{2, 3, 4, \ldots, 32\}, returns the set of prime numbers less than or equal to 32, i.e. \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31\}. Then, if Eratosthenes’ sieve were a sieve function, there should exist a set of prime numbers \mathcal{P} and a real number z \gt 1 such that:
But, if we don’t want the result to be a coincidence, we have to make sure that the function behaves like the algorithm, i.e. that it takes into account the same sets to count the elements. So we should have that:
Clearly \mathcal{P} and z should be chosen so that the prime numbers considered are 2, 3 and 5, i.e. the same as in the algorithm. A possible choice would be, for example, \mathcal{P} = \mathbb{P} and z = 6 (z = 5 does not work because the sieve function considers prime numbers strictly less than z, so if it were z = 5 the function would not consider 5). However, with this choice, or with equivalent choices, we would have:
The set obtained would be identical to the result of the sieve of Eratosthenes without 2, 3 and 5, i.e. without the prime numbers used in the sieve. This difference depends on the fact that the sieve of Eratosthenes, for each prime p considered, eliminates only the multiples of p greater than itself (see step a. of the algorithm ), while the sieve function eliminates all numbers divisible by p, including p itself. So, if we want to express the sieve of Eratosthenes as a sieve function, we have to modify it like this:
- Set A : = \{2, 3, 4, \ldots, N\}
- Set p : = 2
- If p \leq \sqrt{N}:
- For each integer n \in A:
- If n is divisible by p, remove it from A
- Put p : = \textrm{first element of }A
- Go back to step 3.
- For each integer n \in A:
- Return A
Compared to before, in step a. we removed the statement “greater than p” and in step b. we replaced “next element of A” with “first element of A“. In fact, starting from 2 which is initially the first element of A, each p taken into consideration is immediately eliminated by A being divisible by itself, therefore, having arrived at step b., this p no longer belongs to A. But it doesn’t make sense to talk about the element of A following an element that no longer exists; the element that was the next in the first algorithm is now the new first element of A.
It can be shown that this algorithm returns the set of prime numbers contained in A greater than \sqrt{N}. In the case of N = 32, it returns the set \{7, 11, 13, 17, 19, 23, 29, 31\}.
What steps does the algorithm execute for N = 32?
If N = 32, the previous algorithm performs the following steps:
- 1. A : = \{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, 31, 32\}
- 2. p : = 2
- 3. The condition “2 \leq \sqrt{32}” is true
- a. 2 \in A
- i. The condition “2 is divisible by 2” is true
- A = \{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, 31, 32\}
- a. 3 \in A
- i. The condition “3 is divisible by 2” is false
- a. 4 \in A
- i. The condition “4 is divisible by 2” is true
- A = \{3, 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, 31, 32\}
- a. 5 \in A
- i. The condition “5 is divisible by 2” is false
- a. 6 \in A
- i. The condition “6 is divisible by 2” is true
- A = \{3, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32\}
- …
- a. 32 \in A
- i. The condition “32 is divisible by 2” is true
- A = \{3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31\}
- b. p : = 3
- 3. The condition “3 \leq \sqrt{32}” is true
- a. 3 \in A
- i. The condition “3 is divisible by 3” is true
- A = \{5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31\}
- a. 5 \in A
- i. The condition “5 is divisible by 3” is false
- a. 7 \in A
- i. The condition “7 is divisible by 3” is false
- a. 9 \in A
- i. The condition “9 is divisible by 3” is true
- A = \{5, 7, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31\}
- a. 11 \in A
- i. The condition “11 is divisible by 3” is false
- a. 13 \in A
- i. The condition “13 is divisible by 3” is false
- …
- a. 27 \in A
- i. The condition “27 is divisible by 3” is true
- A = \{5, 7, 11, 13, 17, 19, 23, 25, 29, 31\}
- a. 29 \in A
- i. The condition “29 is divisible by 3” is false
- a. 31 \in A
- i. The condition “31 is divisible by 3” is false
- b. p : = 5
- 3. The condition “5 \leq \sqrt{32}” is true
- a. 5 \in A
- i. The condition “5 is divisible by 5” is true
- A = \{7, 11, 13, 17, 19, 23, 25, 29, 31\}
- a. 7 \in A
- i. The condition “7 is divisible by 5” is false
- a. 11 \in A
- i. The condition “11 is divisible by 5” is false
- …
- a. 25 \in A
- i. The condition “25 is divisible by 5” is true
- A = \{7, 11, 13, 17, 19, 23, 29, 31\}
- a. 29 \in A
- i. The condition “29 is divisible by 5” is false
- a. 31 \in A
- i. The condition “31 is divisible by 5” is false
- b. p : = 7
- 3. The condition “7 \leq \sqrt{32}” is false
- 4. Return \{7, 11, 13, 17, 19, 23, 29, 31\}
When we talk about the sieve of Eratosthenes in sieve theory, we are referring to the latter version, not to the original one conceived by the Greek mathematician. This might seem strange, but we must consider that sieve theory was conceived many centuries later; moreover, simplifications are usually made in theories, and it is easier to eliminate all multiples of p without distinction, than to eliminate all of them with the exception of p. Clearly there is an ambiguity because both versions are called “sieve of Eratosthenes”, but it is generally clear from the context which one is being referred to.
The sieve function corresponding to the second version of Eratosthenes’ sieve is as follows:
Why z = \sqrt{ N + 1} and not \sqrt{N}?
The “+1” under the square root is required if N is the square of a prime number. The problem is that in the definition of sieve function only prime numbers strictly smaller than z are considered, so if z exactly coincides with the square root of N and if this were in turn equal to a prime number q, such q would not be considered. If this were the case, the sieve function would behave differently from Eratosthenes’ sieve algorithm, because the latter instead considers all prime numbers less or equal than the square root of N, thus including q.
Instead the choice of z = \sqrt{N + 1} is always correct, in fact:
- If q is a prime number less than or equal to \sqrt{N}, then q = \sqrt{q^2} \lt \sqrt{ q^2 + 1} \leq \sqrt{N + 1} = z, therefore q \lt z and therefore q would be considered in the sieve function, as in Eratosthenes’ sieve algorithm. Since q is arbitrary, we can conclude that all prime numbers less than or equal to \sqrt{N} are considered, both in the sieve of Eratosthenes algorithm and in the corresponding sieve function.
- If q is a prime number greater than \sqrt{N}, then q^2 is greater than N, so greater than or equal to N + 1. But q^2 \geq N + 1 \Rightarrow q \geq \ sqrt{N + 1} = z, so it’s not true that q \lt z. We can therefore conclude that no prime number greater than \sqrt{N} is considered in the sieve function (2), as it happens in the sieve of Eratosthenes.
Summing up the two cases, we can say that all and only the prime numbers less than or equal to the square root of N are considered in the sieve function (2), just like in the corresponding algorithm.
Finally we can observe that, if we replace “less than z” with “less than or equal to z” in Definition C.1, then the choice of z : = \sqrt{N} would be correct (i.e. matching the algorithm). However, we have preferred to maintain the universally accepted definition of sieve function, even if it leads to the choice of z : = \sqrt{N + 1} which we consider less intuitive.