Sieve of Eratosthenes

Learn about the Sieve of Eratosthenes approach to check whether the given number is prime or not.

We'll cover the following

The Sieve of Eratosthenes approach

We can improve our solution and have a low time complexity as compared to the previous solution that we discussed. 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.

We can use a Sieve of Numbers up to N. For all prime numbers <= sqrt(N), we can make their multiple non-prime, i.e., if p is prime, 2p, 3p, … so on will be non-prime.

Let us look at an illustration to understand the approach better.

So now you must have an idea of how this approach works. Let us start the implementation of this approach.

Press + to interact
#include <iostream>
using namespace std;
bool isPrime(int N)
{
    int p[N+1];
    for(int i = 2;i<=N;i++)
        p[i] = 1;
    for(int i = 2;i<=N;i++)
    {
        if(p[i])
            for(int j = 2*i;j<=N;j+=i)
                p[j] = 0;
    }
    p[1] = 0;
    p[0] = 0;
    return (p[N] == 1) ? true : false;
}
int main(){
    int N = 13;
    if(isPrime(N))
        cout << "It is a Prime Number";
    else
        cout << "It is a Non-Prime Number";
}

Explanation:

  • On line 6, we created our Sieve of Numbers p such that the value stored at the ithi^{th} index of p will denote whether i is a prime or not.
  • On line 7, we ran a loop to mark all the numbers as prime initially.
  • From lines 9 to 14, we ran a loop to mark all the multiples of i — that are less than or equal to N — as non-prime. We do this only if the number i is marked as a prime in our sieve array p.
  • On lines 15 and 16, we finally mark 0 and 1 as non-prime.
  • On line 17, we returned true or false based on whether the number is marked as prime or not in our sieve.