Sieve of Eratosthenes: the algorithm for finding the prime numbers in a list

Tutoring: Eratosthenes Sieve - find the prime numbers in a list by removing all the multiples of smaller prime numbers

The Greek mathematician ERATOSTENE (275 - 194 BC) has applied a novel and easy method to determine whether the numbers in a list are prime or not. Starting from the known small prime numbers, 2, 3, 5, 7, 11, 13, 17, 21, etc. it is clear that all their multiples are not prime but composed numbers since a prime has only two divisors: 1 and the number itself. He has ordered a list of natural numbers in ascending order and then he removed all the multiples of the first prime numbers to identify the rest of the larger prime numbers in that list. We will exemplify this method below on a list of numbers ranging from 2 to 100:

  • Number 2 is prime, so we remove from this string all the multiples of 2: 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 2 × 50 = 100. 2 × 51 = 102, is greater than 100, so we stop.
  • Multiples of 2 to remove 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 (two-by-two numbers).
  • 3 is the next prime number, so we will remove from the list all the multiples of 3: 3 × 2 = 6 (which has already been removed from the list, being a multiple of 2); 3 × 3 = 9; 3 × 4 = 12 (which has already been removed from the list, being a multiple of 2); 3 × 5 = 15; 3 × 6 = 18 (which has already been removed from the list, being a multiple of 2); ... and so on up to: 3 × 33 = 99. 3 × 34 = 102, is greater than 100 so we stop.
  • Multiples of 3 to remove 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 (three-by-three numbers). If we don't look at the multiples of 2 that have already been removed from the list, we still have: 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93, 99, ie. numbers that have as factors only prime numbers greater than or equal to 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 will also proceed with the following prime number, 5: 5 × 2 = 10 (which has already been removed from the list, being a multiple of 2); 5 × 3 = 15 (which has already been removed from the list, being a multiple of 3); 5 × 4 = 20 (which has already been removed from the list, being a multiple of 2); 5 × 5 = 25; 5 × 6 = 30 (which has already been removed from the list, being both a multiple of 2 and 3); 5 × 7 = 35; ... and so on up to: 5 × 20 = 100 (which has already been removed from the list, being a multiple of 2). 5 × 21 = 105, is greater than 100, so we stop.
  • Multiples of 5 to remove from the list: 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100 (five-by-five numbers). If we don't look at the multiples of 2 and 3, that have already been removed from the list, we still have to remove: 25, 35, 55, 65, 85, 95, ie. exactly the numbers that have as factors only prime numbers 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 do the same with the following prime number, 7: 7 × 2 = 14 (which has already been removed from the list, being a multiple of 2); 7 × 3 = 21 (which has already been removed from the list, being a multiple of 3); 7 × 4 = 28 (which has already been removed from the list, being a multiple of 2); 7 × 5 = 35 (which has already been removed from the list, being a multiple of 5); 7 × 6 = 42 (which has already been removed from the list, being both a multiple of 2 and 3); ... 7 × 7 = 49; ... and so on up to: 7 × 14 = 98 (which has already been removed from the list, being a multiple of 2). 7 × 15 = 105, is greater than 100, so we stop.
  • Multiples of 7 to remove from the list: 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98 (seven-by-seven numbers). If we don't look at the multiples of 2, 3, and 5, that have already been removed from the list, we still have to remove: 49, 77, 91, ie. exactly the numbers that have as divisors only prime numbers larger 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 from the list the multiples of 11; However, as we have seen above, we should only remove from the list numbers that have as divisors only prime numbers greater than or equal to 11. But already 11 × 11 = 121 is greater than 100, it means that all the numbers left in the list after the process described above are already prime numbers.
  • After removing from the list all the multiples of the prime numbers: 2, 3, 5 and 7, we still have in the list: 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, that is, the list of the prime numbers from 2 to 100.

What is a prime number?

What is a composite number?

Prime numbers up to 1,000

Prime numbers up to 10,000

Sieve of Eratosthenes

Euclid's algorithm

Simplifying ordinary math fractions (reducing to lower terms): steps to follow and examples