Sieve of Eratosthenes Algorithm
Last updated
Last updated
Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number.
The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million or so (Ref Wiki).
Following is the algorithm to find all the prime numbers less than or equal to a given integer n by the Eratosthene’s method: When the algorithm terminates, all the numbers in the list that are not marked are prime.
Let us take an example when n = 100. So, we need to print all prime numbers smaller than or equal to 100.
We create a list of all numbers from 2 to 100.
According to the algorithm we will mark all the numbers which are divisible by 2 and are greater than or equal to the square of it.
Now we move to our next unmarked number 3 and mark all the numbers which are multiples of 3 and are greater than or equal to the square of it.
We move to our next unmarked number 5 and mark all multiples of 5 and are greater than or equal to the square of it.
We move to our next unmarked number 7 and mark all multiples of 7 and are greater than or equal to the square of it.
We continue this process, and our final table will look like below: