Best algorithm to generate all prime numbers up to a given range in C++

In online coding contests, we often come across problems that are related to primality testing. So, why not we should learn about the algorithm, that can generate all possible prime numbers up to a given range. So, let’s learn about it in detail and further, we will implement it in C++.

Sieve of Eratosthenes

  • It is a primality test technique that is used to generate all prime numbers from 2 to n.
  • Time complexity:  O(n log(log(n)))
  • Space complexity: O(n)

Concept

  1. A no, n is prime if none of the smaller numbers from 2 to n-1 divides it.
  2. Firstly we declare a global vector and initialize all of its elements to 1.
  3. Then we mark index 0 and 1 as 0 because 0 and 1 are not prime numbers.
  4. Our main motive is to mark all the non-prime elements present in our global array as 0.
  5. Then upon traversing the global array in smaller to bigger index when we find any prime no i.e., any cell marked as 1, we mark all of its multiple in global array to zero.

Optimization

  1. We will only traverse the global array till the square-root of n.
  2. In the inner loop where we mark all the multiples of a prime no to 0, we will start from the square of the prime no i.e., the cell that is marked 1. This is so because all its multiples that are less than its square would have been already marked as non-prime i.e., 0.

Visualization

sieve

C++ code for the implementation of Sieve of Eratosthenes algorithm.

#include<bits/stdc++.h>
using namespace std;
vector<int>is_prime(1000001, 1); // Global vector to mark all prime no as 1 and non-prime as 0.
// Function to implement sieve of eratosthenes algorithm.
void sieve()
{
    int mn=1e6;
    is_prime[0]=is_prime[1]=0;
    long long int i,j;
    for(i=2; i*i<=mn; i++)
    {
        if(is_prime[i])
        {
            for(j=i*i; j<=mn; j+=i)
            {
                is_prime[j]=0;
            }
        }
    }
}
int main()
{
    sieve();
    int n; // n is the upper range upto which all prime no will be generated.
    cin>>n;
    for(int i=2; i<=n; i++)
    {
        if(is_prime[i])
        {
            cout<<i<<' ';
        }
    }
    return 0;
}

 Input

100

Output

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

If you feel that this article has added any value to your algorithmic knowledge, then please share your valuable feedback in the comment section.

Leave a Reply

Your email address will not be published. Required fields are marked *