Sieve of Eratosthenes
Algorithm that makes it possible to find all the prime numbers up to a given number.
This algorithm is described by these instructions:
To find all of the prime numbers up to a given number n:
- Write a list of all the whole numbers from 1 to n in a table;
- Eliminate 1, which is not a prime number;
- Mark 2 and eliminate all multiples of 2;
- Do the same with 3;
- Choose the next least number not underlined and not eliminated (here, 5);
- Eliminate all of its multiples;
- Repeat the process up to the whole part of the square root of n.
Example
If we want to find all of the prime numbers up to 50, we must first determine the whole part of the square root of 50, which is 7, because the square root of 50 is about 7.07.First, eliminate the number 1. Eliminate all multiples of 2 except 2. Eliminate all multiples of 3 except 3. Eliminate all multiples of 5 except 5. Eliminate all multiples of 7 except 7.
The circled numbers are what is left and they represent the prime numbers up to 50.