Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number.
For example, if n is 10, the output should be “2, 3, 5, 7”. If n is 20, the output should be “2, 3, 5, 7, 11, 13, 17, 19”.

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

Following is the algorithm to find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:

  1. Create a list of consecutive integers from 2 to n: (2, 3, 4, …, n).
  2. Initially, let p equal 2, the first prime number.
  3. Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked.
  4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.

When the algorithm terminates, all the numbers in the list that are not marked are prime.

[ad type=”banner”]

Explanation with Example:
Let us take an example when n = 50. So we need to print all print numbers smaller than or equal to 50.

We create a list of all numbers from 2 to 50

According to the algorithm we will mark all the numbers which are divisible by 2.

Now we move to our next unmarked number 3 and mark all the numbers which are multiples of 3.

We move to our next unmarked number 5 and mark all multiples of 5.

We continue this process and our final table will look like below:

So the prime numbers are the unmarked ones: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

[ad type=”banner”]

Implementation:
Following is C++ implementation of the above algorithm. In the following implementation, a boolean array arr[] of size n is used to mark multiples of prime numbers.

[pastacode lang=”java” manual=”%2F%2F%20Java%20program%20to%20print%20all%20primes%20smaller%20than%20or%20equal%20to%0A%2F%2F%20n%20using%20Sieve%20of%20Eratosthenes%0A%20%0Aclass%20SieveOfEratosthenes%0A%7B%0A%20%20%20%20void%20sieveOfEratosthenes(int%20n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Create%20a%20boolean%20array%20%22prime%5B0..n%5D%22%20and%20initialize%0A%20%20%20%20%20%20%20%20%2F%2F%20all%20entries%20it%20as%20true.%20A%20value%20in%20prime%5Bi%5D%20will%0A%20%20%20%20%20%20%20%20%2F%2F%20finally%20be%20false%20if%20i%20is%20Not%20a%20prime%2C%20else%20true.%0A%20%20%20%20%20%20%20%20boolean%20prime%5B%5D%20%3D%20new%20boolean%5Bn%2B1%5D%3B%0A%20%20%20%20%20%20%20%20for(int%20i%3D0%3Bi%3Cn%3Bi%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20prime%5Bi%5D%20%3D%20true%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20for(int%20p%20%3D%202%3B%20p*p%20%3C%3Dn%3B%20p%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20prime%5Bp%5D%20is%20not%20changed%2C%20then%20it%20is%20a%20prime%0A%20%20%20%20%20%20%20%20%20%20%20%20if(prime%5Bp%5D%20%3D%3D%20true)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Update%20all%20multiples%20of%20p%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for(int%20i%20%3D%20p*2%3B%20i%20%3C%3D%20n%3B%20i%20%2B%3D%20p)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20prime%5Bi%5D%20%3D%20false%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Print%20all%20prime%20numbers%0A%20%20%20%20%20%20%20%20for(int%20i%20%3D%202%3B%20i%20%3C%3D%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if(prime%5Bi%5D%20%3D%3D%20true)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(i%20%2B%20%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20%20%0A%20%20%20%20%2F%2F%20Driver%20Program%20to%20test%20above%20function%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%2030%3B%0A%20%20%20%20%20%20%20%20System.out.print(%22Following%20are%20the%20prime%20numbers%20%22)%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22smaller%20than%20or%20equal%20to%20%22%20%2B%20n)%3B%0A%20%20%20%20%20%20%20%20SieveOfEratosthenes%20g%20%3D%20new%20SieveOfEratosthenes()%3B%0A%20%20%20%20%20%20%20%20g.sieveOfEratosthenes(n)%3B%0A%20%20%20%20%7D%0A%7D” message=”Java Program” highlight=”” provider=”manual”/]

Output:

Following are the prime numbers below 30
2 3 5 7 11 13 17 19 23 29