Sieve of Eratosthenes
Finding All Prime Numbers
For a given number n, print all primes <= n. Also, n is a small number. Prime numbers are only divisible by themselves and 1.
2 3 5 7
There are only 4 prime numbers less than or equal to 10.
1. Iterate from 2 to N.
2. Check for prime numbers.
3. Print the number if it is a prime number.
Here, N = number
1. Write all the numbers from 2,3,4…n.
2. Take 1st prime number and mark all of its multiples as visited.
Efficient Approach: Sieve of Eratosthenes
3. Now, take the next unvisited number and follow step 2 with that number.
4. Numbers that remain unmarked at the end of the algorithm are prime numbers.
How to implement the solution in different languages?