The Sieve of Eratosthenes: The algorithm is used to find (identify) the prime numbers in a list. Tip: start by crossing out the multiples of the smaller primes

The Greek mathematician ERATOSTENE (275 - 194 BC) used a new for that time and simple method to determine whether the numbers in a list are prime or not.
He started with the known small prime numbers 2, 3, 5, 7, 11, 13, 17, 23, etc. It is obvious that all their multiples are not prime numbers but composite ones.

He arranged a list of natural numbers in ascending order. Then he identified and removed all the larger composite numbers in this list as they are multiples of the first primes and thus setting apart the larger primes in this list.
We illustrate this method below, with a list of numbers sorted in ascending order, from 2 to 100:

The number 2 is a prime number, so we first identify all the multiples of 2 in the list:
2 × 2 = 4
2 × 3 = 6
2 × 4 = 8
2 × 5 = 10
2 × 6 = 12
2 × 7 = 14
2 × 8 = 16
2 × 9 = 18
2 × 10 = 20
... and so on, up to the number: 2 × 50 = 100.
The number 2 × 51 = 102, is larger than 100, so we can stop.
Remove all the multiples of the number 2 from the list: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100.

The number 3 is a prime number, so we identify all the multiples of 3 in the list:
3 × 2 = 6 (This number has already been removed from the list, it is a multiple of 2);
3 × 3 = 9
3 × 4 = 12 (This number has already been removed from the list, it is a multiple of 2);
3 × 5 = 15
3 × 6 = 18 (This number has already been removed from the list, it is a multiple of 2);
... and so on, up to the number: 3 × 33 = 99.
The number 3 × 34 = 102, is larger than 100, so we can stop.
Remove all the multiples of the number 3 from the list: 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 97, 99.
If we have already removed all the multiples of the number 2 from the list, we are only left with: 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93. 99. These numbers are written below, as multiples of the number 3:
3 × 3 = 9
3 × 5 = 15
3 × 7 = 21
3 × 9 = 3 × 3 × 3 = 27
3 × 11 = 33
3 × 13 = 39
3 × 15 = 3 × 3 × 5 = 45
3 × 17 = 51
3 × 19 = 57
3 × 21 = 3 × 3 × 7 = 63
3 × 23 = 69
3 × 25 = 3 × 5 × 5 = 75
3 × 27 = 3 × 3 × 3 × 3 = 81
3 × 29 = 87
3 × 31 = 93
3 × 33 = 3 × 3 × 11 = 99.

We then proceed with the following prime number, 5:
5 × 2 = 10 (This number has already been removed from the list - it is a multiple of 2);
5 × 3 = 15 (This number has already been removed from the list - it is a multiple of 3);
5 × 4 = 20 (This number has already been removed from the list - it is a multiple of 2);
5 × 5 = 25
5 × 6 = 30 (This number has already been removed from the list - it is a multiple of 2 and 3);
5 × 7 = 35
... and so on, up to the number: 5 × 20 = 100 (This number has already been removed from the list - it is a multiple of 2).
The number 5 × 21 = 105, is larger than 100, so we can stop.
Remove all the multiples of the number 5 from the list: 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100.
If we are not looking after the multiples of 2 and 3, that have already been removed from the list, we are still left with these numbers to remove: 25, 35, 55, 65, 85, 95, ie. exactly those numbers that have in their prime factorization only prime factors greater than or equal to 5:
5 × 5 = 25
5 × 7 = 35
5 × 11 = 55
5 × 13 = 65
5 × 17 = 85
5 × 19 = 95.

Then we repeat the process with the next prime number 7:
7 × 2 = 14 (the number has already been removed from the list - it is a multiple of 2);
7 × 3 = 21 (the number has already been removed from the list - it is a multiple of 3);
7 × 4 = 28 (the number has already been removed from the list - it is a multiple of 2);
7 × 5 = 35 (the number has already been removed from the list - it is a multiple of 5);
7 × 6 = 42 (the number has already been removed from the list - it is a multiple of 2 and 3);
7 × 7 = 49
... and so on, up to the number: 7 × 14 = 98 (the number has already been removed from the list - it is a multiple of 2).
7 × 15 = 105, is larger than 100, so we can stop.
Remove all the multiples of the number 7 from the list: 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98.
If we are not looking after the multiples of 2, 3, and 5, that have already been removed from the list, we still have to remove: 49, 77, 91. These are precisely the numbers that have in their prime factorizations prime factors that are greater than or equal to 7:
7 × 7 = 49
7 × 11 = 77
7 × 13 = 91.

The next prime number in the list is 11 and we should remove the multiples of 11 from the list.
However, as we saw in the steps above, we should only attempt to remove from the list numbers having in their factorizations prime factors that are greater than or equal to 11.
But already 11 × 11 = 121, which is greater than 100.
This means that all the numbers that remained in the list after performing the steps above are already prime numbers.

The list of primes consists of the non-removed numbers.
After removing from the list all the multiples of the prime numbers 2, 3, 5, and 7, we are left in the list with these numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 - the list of the prime numbers from 2 to 100.

Some articles on the prime numbers