# 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.