Sieve of Eratosthenes: eliminate prime numbers multiples from a list, up to given limit

Tutoring: Eratosthenes Sieve - identifying the prime numbers in a list up to a given limit by removing all their multiples

Greek mathematician Eratosthenes (275-194 BC) introduced more than 2000 years ago the sieve of Eratosthenes, an efficient method of easily identifying prime numbers.

Let's look at the range of natural numbers from 2 to 100, in ascending order, as a list. Remove from this list all the prime numbers' multiples, as it follows:

  • number 2 is prime, so we remove from the list all its multiples;
  • number 3 is prime, so we also remove all its multiples;
  • we then proceed with 5;
  • then, 7's multiples are also removed;
  • the next prime number is 11, but since 7 × 7 = 49, which is less than 100, and 11 × 11 = 121, which is larger than 100, then the numbers that remained in our list after removing the multiples are all prime;
  • Multiples of 2: 4, 6, 8, 10, 12, 14, 16, 18, 20, ... 100
  • Multiples of 3: 6, 9, 12, 15, 18, 21, 24, 27, ... 99
  • Multiples of 5: 10, 15, 20, 25, 30, 35, 40, 45, ... 100
  • Multiples of 7: 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98
  • Once we get rid of all the multiples of 2, 3, 5 and 7, the only numbers that are left are: 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, exactly the list of prime numbers from 2 up to 100.

What is a prime number?

What is a composite number?

Sieve of Eratosthenes

Euclid's algorithm

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