SIEVE OF ERATOSTHENES - AN EFFICIENT PRIME GENERATING ALGORITHM

SIEVE OF ERATOSTHENES:

One of the efficient sieve algorithms to identify primes up to a given number.

The naive approach gives a time complexity of O(N*sqrt(N)).

But this algorithm finds the prime at a complexity of  O(log log(N)sqrt(N)).

My reference:

1. Youtube

Source code:

       
#include<iostream>

#include<bits/stdc++.h>

using namespace std;

void find_primes(int num){

    ///construct a boolean array which checks whether a number is prime or not....

      bool primes[num+1];

      memset(primes,true,sizeof(primes));///initializing array with true...considering all numbers to be prime

      primes[0] = false;///0 is not a prime

      primes[1] = false;///1 is not a prime

      for(int i = 2 ; i * i <= num;i++){///start from 2 and run upto sqrt(num)

          if( primes[i] ){

              for(int j = i*2;j <= num;j += i){

                  ///multiples of i are not prime numbers..so making them false...

                  primes[j] = false;

              }

          }

      }

      for(int i = 0; i <= num; i++){

          if( primes[i] )

              cout << i <<"\n";

      }

}

int main(){

    int num;

    cout << "Find prime upto which number";

    cin >> num;

    find_primes(num);

}