Sieve of Eratosthenes

Sieve of Eratosthenes is one of the fastest and most efficient ways to find all the prime numbers up to a given limit. It works by iteratively crossing out the composite numbers (i.e., multiples of other primes) starting from 2, the first prime number.

Explanation: The algorithm starts with a list of all numbers from 2 to N, where N is the upper bound of the primes we want to find. Then, it iteratively sieves out all the composite numbers from the list starting from 2, progressing to the next smallest not yet marked prime number. By the end of the algorithm, all the remaining unmarked numbers are primes.

Implementation: Here is an implementation of Sieve of Eratosthenes in C++ that finds all the prime numbers from 2 to N.


#include <iostream>
#include <vector>
using namespace std;

vector<bool> isPrime;

void sieveOfEratosthenes(int n) {
    isPrime.resize(n + 1, true); //marking all numbers till N as prime initially

    isPrime[0] = false; // 0 is not a prime number
    isPrime[1] = false; // 1 is not a prime number

    for(int i = 2; i <= n; i++) {
        if(isPrime[i]) {
            for(int j = i * 2; j <= n; j += i) {
                isPrime[j] = false; //marking multiple of the prime number as not prime.
            }
        }
    }
}

int main() {
    int n;
    cin >> n;

    sieveOfEratosthenes(n);

    cout << "Prime numbers from 2 to " << n << " are: ";
    for(int i = 2; i <= n; i++) {
        if(isPrime[i]) {
            cout << i << " ";
        }
    }
    cout << endl;

    return 0;
}

In this implementation, we have used a boolean vector isPrime to store whether each number up to n is prime or not. We have initialized all the values true initially.

The sieveOfEratosthenes function takes an integer n as input and cross out all the composite numbers from the list starting from 2 to n by marking its multiples of the prime as false.

The main function reads the input value n, invokes the sieveOfEratosthenes function to compute all the primes up to n, and then prints all the prime numbers to the console.

This implementation is just one way of implementing the Sieve of Eratosthenes in C++. Different implementations may be better suited for different applications, depending on factors like the size of the input n, the desired speed and memory usage, and the specific operations you plan to execute on the prime numbers later on.

The time complexity of the Sieve of Eratosthenes algorithm is O(n log log n) where n is the upper limit of the prime numbers we want to find. This complexity is reasonable because it performs only a fixed number of operations on each number up to n, and there are O(log log n) primes up to n.

The implementation complexity of the algorithm involves the initialization of the boolean vector isPrime, which takes O(n) time. The outer loop iterates O(log log n) times, and the inner loop iterates roughly same number of times of outer loop O(log log n) too. Therefore, the overall time complexity of the algorithm is O(n log log n). This makes the Sieve of Eratosthenes one of the fastest and most efficient algorithms to compute all the prime numbers up to a specified limit.

PRACTICE PROBLEMS ;

Count Primes

Distinct Prime Factors of Product of Array