More
    AlgorithmsSieve of Eratosthenes

    Sieve of Eratosthenes

    Sieve of Eratosthenes Algorithm is an algorithm to find all prime numbers between two numbers or all prime numbers less than or equal to a number, with the most efficient approach having time complexity O(n*log(log(n))) for a given number (n). This algorithm basically use a array or vector to store whether a number is prime or not. And deals with the indices to set a number as prime or composite.

    How Sieve of Eratosthenes works:

    1. First, we declare an array/vector of size n (here n is the number up to which we have to find prime numbers) and set all elements of the array to 1.
    2. Then we iterate from i=2 to square root of n and for every iteration there is a nested loop which iterate through the i to square root of n, which sets every array index which is a multiple of the number to 0. This runs till the i become square root of n.
    3. When this nested loop ends all the non-prime numbers having value 0 because we set the multiples as 0. So, automatically we found the prime number as those array index which having value 1.

    Here’s an implementation for the above approach:


    In C++:

    #include<iostream>
    #include<vector>
    using namespace std;
    void Print_prime(vector<int> arr,int n) // Declaration of a function to calculate prime numbers
    {
       arr[0]=0;// as we know 0 can never be prime so set its value to 0
       arr[1]=0;// as we know 1 can never be prime so set its value to 0
       /*
       declaration of nested loop which sets the multiples
       of every i to 0 (as we know a prime number has no factors than 1 or itself)
       */
       for(int i=2;i*i<=n;i++)
       {
          if(arr[i]==1)
          {
           for(int j=i;j*i<=n;j++)
           {
               arr[i*j]=0; // setting all non-prime numbers to 0
           }
          }
       }
       cout<<"All Prime Numbers Till "<<n<<"\n";
       // printing all prime numbers (array elements that have value = 1)
       for(int i=0;i<n;i++)
       {
           if(arr[i]==1)
             cout<<i<<" ";
       }
    }
    int main()
    {
      cout<<"Enter the number till You want to print all prime"<<"\n";
      int number;
      cin>>number;
      vector<int> arr(number,1); // declare a vector and set value 1 to every element of the vector
      Print_prime(arr,number); // calling function to print all prime till n
      return 0;
    }
    

    Input:

    Enter the number till You want to print all prime
    15

    Output:

    All Prime Numbers Till 15
    2 3 5 7 11 13
    

    A modified implementation for this algorithm is:


    In C++:

    #include<iostream>
    #include<vector>
    using namespace std;
    void Print_prime(vector<int> arr,int beg,int n) // Declaration of a function to calculate prime numbers
    {
       arr[0]=0;// as we know 0 can never be prime so set its value to 0
       arr[1]=0;// as we know 1 can never be prime so set its value to 0
       /*
       declaration of nested loop which sets the multiples
       of every i to 0 (as we know a prime number has no factors than 1 or itself)
       */
       for(int i=2;i*i<=n;i++)
       {
          if(arr[i]==1)
          {
           for(int j=i;j*i<=n;j++)
           {
               arr[i*j]=0; // setting all non-prime numbers to 0
           }
          }
       }
       cout<<"All Prime Numbers In this range "<<n<<"\n";
       // printing all prime numbers (array elements that have value = 1)
       for(int i=beg;i<=n;i++)
       {
           if(arr[i]==1)
             cout<<i<<" ";
       }
    }
    int main()
    {
      cout<<"Enter the number range You want to print all prime"<<"\n";
      int number1,number2;
      cin>>number1>>number2;
      vector<int> arr(number2+1,1); // declare a vector and set value 1 to every element of the vector
      Print_prime(arr,number1,number2); // calling function to print all prime till n
      return 0;
    }

    Input:

    Enter the number range You want to print all prime
    2   25
    

    Output:

    All Prime Numbers In this range
    2 3 5 7 11 13 17 19 23
    

    This article is exclusively contributed by Amit Singh Bisht.

    Read Next: Functions, Prototypes & Recursion in C++

    Sponsored

    4 COMMENTS

    LEAVE A REPLY

    Please enter your comment!
    Please enter your name here

    Subscribe Today

    GET EXCLUSIVE FULL ACCESS TO PREMIUM CONTENT

    Get unlimited access to our EXCLUSIVE Content and our archive of subscriber stories.

    Exclusive content

    Latest article

    More article