Sieve of Eratosthenes : Find all Prime Numbers

Problem Statement: Sieve of Eratosthenes – Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number.

Examples:

Example 1:
Input: n =10 
Output: 2 3 5 7

Example 2: 
Input: n = 20 
Output: 2 3 5 7 11 13 17 19

The sieve of Eratosthenes is a very popular and efficient algorithm to find all primes less than number n.

We can find primes less than n using a loop also, but for bigger inputs, this method might take a lot of time, so in order to tackle that, we have come up with this algorithm, sieve of Eratosthenes –

It basically works like a sieve, we just filter the numbers in each iteration, to make our search space smaller and smaller, which makes this more efficient.

So the algorithm is –

1. From 1 to n, leaving 1, we will start from 2 to n, and mark numbers which are multiples of 2.

2. Perform this above step till the nth number

3. Then we will have some unmarked numbers left, which are eventually the prime numbers because they are not divisible by any other number. And we get our answer.

For example – n = 10

4 5 6

7 8 9

In the first pass, we will start from 2, marking the numbers divisible by 2.

4 5 6

7 8 9

Now in the second pass, marking the numbers divisible by 3, 6 is already marked.

4 5 6

7 8 9

Now in the third pass, we will mark the numbers divisible by 5, 10 is already marked

4 5 6

7 8 9

Now, check for 7, mark numbers divisible by 7.

So the final situation is –

4 5 6

7 8 9

The unmarked numbers are – 2,3, 5, 7 and we have the answer.

We can take a boolean array to mark as true or false, and the indexes of the array will be represented as numbers.

Code:

C++ Code

#include <bits/stdc++.h>

using namespace std;
void SieveOfEratosthenes(int n) {
  bool prime[n + 1]; //creating a boolean array 
  memset(prime, true, sizeof(prime)); //initially set every value to true 
  for (int p = 2; p * p <= n; p++) {
    if (prime[p] == true) {
      for (int i = p * p; i <= n; i += p) 
  //check for all multiples of p less than n or squares of p and mark them false 
        prime[i] = false;
    }
  }
  // Print all prime numbers whose values are still true 
  for (int p = 2; p <= n; p++)
    if (prime[p] == true)
      cout << p << " ";
}
int main() {
  int n = 30;
  cout << "The prime numbers less than equal to " << n << " are" << endl;
  SieveOfEratosthenes(n);
  return 0;
}

Output:

The prime numbers less than equal to 30 are
2 3 5 7 11 13 17 19 23 29

Time Complexity – O(n*(log(log(n))))

Space Complexity – Auxiliary Space – O(n)

Java Code

import java.util.*;

class TUF {
  static void SieveOfEratosthenes(int n) {
    boolean prime[] = new boolean[n + 1]; //creating a boolean array 
    Arrays.fill(prime, true); //initially set every value to true 
    for (int p = 2; p * p <= n; p++) {
      if (prime[p] == true) {
        for (int i = p * p; i <= n; i += p) 
    //check for all multiples of p less than n or squares of p and mark them false 
          prime[i] = false;
      }
    }
    // Print all prime numbers whose values are still true 
    for (int p = 2; p <= n; p++)
      if (prime[p] == true)
        System.out.print(p + " ");
  }
  public static void main(String args[]) {
    int n = 30;
    System.out.println("The prime numbers less than equal to " + n + " are ");
    SieveOfEratosthenes(n);
  }
}

Output:

The prime numbers less than equal to 30 are
2 3 5 7 11 13 17 19 23 29

Time Complexity – O(n*(log(log(n))))

Space Complexity – Auxiliary Space – O(n)

Special thanks to Ishita Dhiman for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article