Coders Packet

Implementation of Sieve of Eratosthenes using C++

By Vaishnavi Jaiswal

This packet consists of a C++ code based on the implementation of the Sieve of Eratosthenes.

Hello everyone,

Suppose we want to find all prime numbers less than or equal to a number n. Then we can do so by using multiple approaches. Like first we can try to solve this problem by using the brute force method or the naive method.

Approach: Brute Force method                   

In this brute force method, firstly, we will use a loop to iterate from 0 to n and for each number, we will do a prime-check. To check if a number is prime or not, we simply check if its divisors include anything other than 1 and the number itself. If so, then it is not a prime number. To implement this, we will require one more loop inside the previous loop and it will apparently increase the overall time complexity. The iteration itself has O(n) time complexity and for each iteration, we have to check for prime which will again take O(√n)(here we will check only till √n because if a number doesn't have any factors up to √n then it won't have factors beyond that too). So this method is not feasible for larger values of n because it will exceed the time limit. It will only work for smaller values of n. Therefore, we need a more efficient solution.

Approach: Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm in mathematics used to find all prime numbers less than or equal to a given number n when n is smaller than 10 million or so. In this algorithm, firstly, we will create a list of consecutive integers from 2 to n. Then we will start with the smallest prime number 2 and mark all of its multiples up to "n" as non-primes. Then we will repeat the same process for the next available number in the list that is not marked as composite or non-prime.

ALGORITHM

1. In the first step, create a list of consecutive integers from 2 to n and mark all of them as true.

2. Let i be the variable we use in the outer loop to iterate from 2 to n. Initially, set the value of i equal to 2 because 2 is the smallest prime number.

3.Now iterate over the multiples of i by counting in increments of i from i*i to n and mark them as false if they are previously marked as true. Also, i       must be true.

4. In this step, find the smallest number in the list greater than i that is not marked as false. Stop, if there is no such number. Otherwise, let i be now equal to the next prime and repeat the process from step 3.

5. At last, when the algorithm terminates, all of the remaining numbers marked as true in the list are prime numbers.

Time Complexity of the above algorithm is:- O(n*loglogn)

Here is the C++ code used to implement the above algorithm.

#include<bits/stdc++.h>
using namespace std;
void Sieve ()
{
  int n;
  cout << "Enter a number";
  cin >> n;
  // Create a boolean array,here it is a vector of bool type and initialize all its entries as true.
  // A value in P[i] will finally be false if i is not a prime, else true.  
  vector < bool > P (n + 1, true);
  for (long long i = 2; i<=n; i++)
    {
      // If P[i] is not changed,then it is a prime
      if (P[i] == true)
  {
    //Now mark all the multiples of i as false which are previously marked as true
    for (long long j=i*i; j<=n; j=j+i)
      {
        if (P[j] == true)
    {
      P[j] = false;
    }
      }
  }
    }
    // Print all prime numbers
  cout << "The prime numbers less than or equal to " << n << " are:" << endl;
  for (int i = 2; i<=n; i++)
    {
      if (P[i])
    {
    cout << i << " ";
    }
    }
}

//Driver code
int main ()
{
  Sieve ();
  return 0;
}

About the code

At the beginning of the code, I had created a vector of bool type and initialized all its entries as true. A value in this vector will be false only for a non-prime number, else true. Then, there is a function named void Sieve(). Inside this function, there is a nested loop structure, the outer loop starts from 2 and runs up to n. Now, before entering the inner loop we will pick the next available prime number. The index we picked suppose is i, then the inner loop will start from j=i*i and increase by increments of i(j=j+i) until it surpasses n. In short, we iterate over every multiple of i between i and n. Then check if P[j] is true or not, if it is true, make it false. Then at the end of the void Sieve() function, I had printed out all the remaining numbers from 2 to n which are marked as true in the list. These are the required prime numbers. In the end, inside the main function, we will call the Sieve function. 

for (long long i = 2; i <= n; i++)

The outer loop can run from i=2 to i<=sqrt(n) instead of i<=n because, by that point, we would have considered all the possible multiples of all the prime numbers below n. This will further optimize the solution and slightly decrease the overall time complexity.

Download project

Reviews Report

Submitted by Vaishnavi Jaiswal (Vaishnavi0904)

Download packets of source code on Coders Packet