The sieve of Erathostenes and the formal definition of sieve

Prerequisites:

• The definition of prime number
• Chen’s Theorem: statement and introduction to the proof

In the previous article we saw that the proof of Chen’s Theorem is based on sieve theory. But what is a sieve? In this article we’ll explain it based on the most famous example of a sieve, that 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:

To better understand this Property, let’s consider the equivalent statement obtained by inverting the implication:

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}.

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:

1. Set P : = \{\}
2. For any integer n between 2 and N:
   1. Set p : = 2 and d := 1
   2. If p \leq \sqrt{n} and d = 1:
      1. If n is divisible by p, set d : = p
      2. Otherwise, set p : = \textrm{next element of }P
      3. Go back to step b.
   3. If d = 1, add p to the set P
3. Return P

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:

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:

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.

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:

1. Set A : = \{2, 3, 4, \ldots, N\}
2. Set p : = 2
3. If p \leq \sqrt{N}:
   1. For any integer n \in A greater than p:
      1. If n is divisible by p, delete n from A
   2. Put p : = \textrm{next element of }A
   3. Go back to step 3.
4. 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.

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:

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:

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.

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:

1. Set A : = \{2, 3, 4, \ldots, N\}
2. Set p : = 2
3. If p \leq \sqrt{N}:
   1. For each integer n \in A:
      1. If n is divisible by p, remove it from A
   2. Put p : = \textrm{first element of }A
   3. Go back to step 3.
4. 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\}.

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: