Sieve of Eratosthenes

In a previous article, we saw how to determine whether a number is a prime or not. Now, let’s see how to find all primes smaller than or equal to n. We can run a loop from 1 to n and for each iteration check whether the loop counter variable is a prime or not. But that would be very inefficient since we would be repeating same calculations over and over again.

In this situation it is best to use a method known as the Sieve of Eratosthenes. The Sieve of Eratosthenes will generate all the primes from 2 to n. It begins by assuming that all numbers are prime. It then takes the first prime number and removes all of its multiples. It then applies the same method to the next prime number. This is continued until all numbers have been processed.

This is a sieve. It’s a utensil used for straining solids from liquids. Eratosthenes has devised such a sieve to strain prime numbers from first N numbers by draining out composite numbers.

Sift the Two’s and Sift the Three’s, The Sieve of Eratosthenes. When the multiples sublime, The numbers that remain are Prime.

Demonstration of Sieve of Eratosthenes when n=120 #

Eddie Woo’s remarkable explanation: #

Now, let’s dive into the code #

#include<bits/stdc++.h> 
#include<cmath>
using namespace std; 

void SieveOfEratosthenes(int n);

int main(void){
    int n;
    cout<<"Enter the value of n: ";
    cin>>n;
    SieveOfEratosthenes(n);
    return 0;
}
void SieveOfEratosthenes(int n){
    bool prime[n+1];
    //assume all nos. are primes
    //mark all of them as true
    memset(prime, true, sizeof(prime));
    //take first prime i.e. 2
    //and mark all of its multiples as false
    //apply same method to the next prime, i++
    //the outer loop finds the next prime 
    //while the inner loop removes all the 
    //multiples of the current prime
    for(int i=2; i<=sqrt(n); i++){
        if(prime[i] == true){
            for(int j=i*i; j<=n; j+=i){
                prime[j] = false;
            }
        }
    }
    printf("Primes <= %d:\n", n);
    for(int i=2; i<=n; i++){
        if(prime[i])
            printf("%d ", i);
    }
    printf("\n");
}

Optimizing it #

Since all even numbers (except 2) are composite, we can stop checking even numbers at all. Instead, we need to operate with odd numbers only. First, it will allow us to half the needed memory. Second, it will reduce the number of operations performing by algorithm approximately in half.

#include<bits/stdc++.h> 
#include<cmath>
using namespace std; 

void SieveOfEratosthenes(int n);

int main(void){
    int n;
    cout<<"Enter the value of n: ";
    cin>>n;
    SieveOfEratosthenes(n);
    return 0;
}

void SieveOfEratosthenes(int n){
    bool prime[n/2];
    memset(prime, false, sizeof(prime));
    //2 is the only even prime
    //hence ignore it
    //skip all other even nos.
    //therefore start check from 3
    //and increment by 2 to check only odd nos.
    //mark true if it's a prime
    for(int i=3; i<sqrt(n); i+=2){
        if(prime[i/2] == false){
            for(int j=i*i; j<n; j+=i*2){ //i*2 to skip the even nos. in the multiplication table of i
                prime[j/2] = true;
            }
        }
    }
    printf("Primes <= %d:\n", n);
    printf("2 ");
    for(int i=3; i<n; i+=2){
        if(!prime[i/2])
            printf("%d ", i);
    }
    printf("\n");
}

References: