ATRACTOR

Let us see, in detail, the operation of the Sieve of Eratosthenes, used to list all prime numbers less than or equal to a certain number.

The starting point is a table with a certain number of rows and a certain number of columns, containing all natural numbers from \(1\) until the number given by the product of the number of rows by the number of columns.

The first step is to mark the number \(1\) as non-prime (since, by definition, \(1\) is not prime). Next, the first unmarked number (that is, the number \(2\)) is marked as a prime and all its multiples are marked as non-prime. Next, the first number of the table not yet marked (neither as a prime nor as a non-prime) is marked as a prime, and all its multiples, not yet marked, are marked as non-prime.

This process is repeated until a situation is reached in which, by marking as a prime the first number of the table not yet marked (neither as prime nor as non-prime), one observes that all its multiples in the table have already been marked previously as non-prime.
Why? What is the first multiple of a prime (different from itself) who is not already marked as non-prime? It is necessarily the product of this prime by itself. Then the situation mentioned occurs for the first prime whose product by itself (the square of the prime) is not in the table. In this case, the first number, different from itself, that admits it as the smallest divisor (different from \(1\)) is not in the table and thus all composite numbers in the table admit a prime divisor less than that number and were already marked as non-prime. For example, in the table \(10\) by \(5\), \(7\times 7 \) is still in the table but \(11 \times 11\) is not, so all multiples of \(11\) in the table have already been marked as non-prime. In the table \(15\) by \(10\), \(11 \times 11\) belongs to the table, while \(13 \times 13\) does not. When one arrives at the situation described above, all the unmarked numbers are prime.

Let us analyze now why this method actually provides all prime numbers not greater than the largest number in the table. First, all numbers marked as non-prime are in fact non-prime: the first number marked as non-prime was \(1\) (which is not prime by definition since it admits only one divisor); all the other marked non-prime numbers are multiples of a number which was previously marked as prime (hence, being multiples of that number, they admit it as a divisor, and of course also admit as divisors \(1\) and itself, being, therefore, composite numbers).

And how can we ensure that the first unmarked number is always prime? Well, if it is the first unmarked number, it means that it is not a multiple of any number except \(1\) less than itself, so it does not admit any divisors other than \(1\) and the number itself, thus being prime.

Note that after the number \(3\) is marked as prime, all its multiples are marked as non-prime; the first number that will be marked as non-prime will be the \(9\) \((3 \times 3)\). Thus, after all multiples of \(3\) are marked as non-prime, we can already guarantee that all unmarked numbers less than \(9\) are prime, which includes, besides the number \(5\), also the number \(7\).

Likewise, after the number \(5\) is marked as prime, the first number that will be marked as non-prime will be the first number that admits \(5\) as its smallest divisor, which is precisely the number \(25\)\((5 \times 5)\). Hence all unmarked numbers less than \(25\) are prime, which includes, besides \(7\), the numbers \(11, 13, 17, 19\) and \(23\).

So we can even guarantee that not only the first unmarked number is prime, but also all unmarked numbers that are smaller than its square are prime.