Algorithms – ‘Sieve of Eratosthenes’ – Find all primes numbers till n

Problem: If input is given n = 20, then print all primes numbers till 20. (Prime = Number which can be divided by exactly 2 dividers i.e. only 1 & itself)

Intuitive approach: Intuitively you can just iterate from 1 to 20 & check if each number is prime or not. But that will be an expensive algorithm.

Sieve of Eratosthenes: Greek mathematician Eratosthenes provided an efficient algorithm to find such prime numbers.

  • First assume all numbers from 2 till 20 are prime.

 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20

  • Then start with 2 & mark all its multiples as not prime. (Strike-through below)

 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 

  • Then go to next prime (Next non strike-through) i.e. 3 & mark its multiples as non-prime. (Strike-through below)

 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 

  • Then go to next prime (Next non strike-through) i.e. 5 & mark its multiples as non-prime. (Strike-through below)

 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 

  • Go on till there are no more next prime remaining & list is over. Remaining numbers will all be primes (Marked in blue).

 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 

Java Code:

Output:

 

Leave a Reply

Your email address will not be published. Required fields are marked *