Sieve of Eratosthenes

It is likely that the algorithm, invented over 2000 years ago by the Greek mathematician Eratosthenes Kirensky, was the first of its kind. His only task is to find all primes up to some given number N. The term “sieve” means filtering, namely, filtering all numbers except prime numbers. Thus, the processing by the algorithm of a numerical sequence will leave only simple numbers, all the components will be eliminated.

Let us consider in general the work of the method. An ordered sequence of natural numbers is given. Following the method of Eratosthenes, we take a certain number P initially equal to 2 - the first prime number, and delete from the sequence all multiples of P: 2P, 3P, 4P, ..., iP (iP≤N). Further, from the resulting list, P is taken as the next number after the two - the triple, deletes all multiples of it (6, 9, 12, ...). According to this principle, the algorithm continues to run for the remainder of the sequence, sifting out all composite numbers in a given range.

The following table contains natural numbers from 2 to 100. Red marks those that are deleted during the execution of the “Sieve of Eratosthenes” algorithm.

Software implementation of the Eratosthenen algorithm will require:

1. organize a logical array and assign it to the elements from the range from 2 to N logical unit;
2. in the free variable P write the number 2, which is the first prime number;
3. remove from the array all the multiples of P ² , stepping in steps of P;
4. write in P the following not crossed out number;
5. repeat the steps described in the two previous paragraphs, as long as possible.

Note: in the third step, we exclude numbers, starting right away from P ² , this is due to the fact that all the composite numbers less than P will already be crossed out. Therefore, the filtering process should be stopped when P ² becomes greater than N. This important remark allows us to improve the algorithm by reducing the number of operations performed.

This is what the pseudo-code of the algorithm will look like:

P ← 2
while P ² ≤N perform
{
i ← P ²
if B [P] = true then
until i≤N perform
{
B [i] ← false
i ← i + P
}
P ← P + 1
}

It consists of two cycles: external and internal. The outer loop is executed until P ² exceeds N. The very same P changes with step P + 1. The inner loop is executed only if at the next step of the outer loop it turns out that the element with the index P is not crossed out. It is in the inner loop that all composite numbers are eliminated.

C ++ program code:

Pascal program code:

The sieve of Eratosthenes to identify all primes in a given sequence limited to some N will require O ( N log (log N )) operations. Therefore, it is more appropriate to use this method than, for example, the most trivial and costly search for dividers.