Sieve of Eratosthenes is an algorithm to find all prime numbers up to a given range. This concept is very important when it comes to competitive programming because it is the most efficient way to find all primes smaller than n until variable n is smaller than 10 million.
Example n = 7 2, 3, 5, 7 n = 15 2, 3, 5, 7, 11, 13
Let us understand how it works
Since a prime number have only two divisors 1 and itself. We will use this concept to find all the prime numbers up to a given range.
- Create a list of all consecutive integers from 2 to n(n is our range).
- Initially let p=2, the first prime number.
- Starting from 2p and mark all the factors of p in the range 2p to n. These factors will be 2p, 3p, 4p, 5p and so on
- Find the next unmarked number greater than p and repeat step 2. If there is no such number stop.
Example
Let’s understand the working of Sieve of Eratosthenes for n = 50. Here we require to print all the prime numbers in the range 2 – 50.
List of all numbers from 2 to 50. Note 1 is neither prime nor not prime.
Let p=2, using step 2, we will mark all the factors of 2 in range 4(2p) to 50 i.e. 2, 4, 8……50.
Now 3 is the next, not marked integer. So, now p=3, using step 2, we will mark all the factors of 3 from 6(3*p) till 50 i.e. 6, 9…….48
Now 5 is the next, not marked integer. So, now p=5, using step 2, we will mark all the factors of 5 from 10(2*p) to 50 i.e. 10, 15 … 50
We will continue this process for all the unmarked integer and our final table will look as represented below.
So, the prime numbers in range 2 to 50 are unmarked one – 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
Implementation of the above algorithm in CPP
#include <bits/stdc++.h> using namespace std; int sieve_of_eratosthenes(int n){ vector<bool> prime(n+1,false); for(int p=2; p<=n; p++) { if(prime[p]==false) { for(int k = 2*p; k<=n; k=k+p) prime[k] = true; } } cout<<"Prime numbers between 2 to "<<n<<":"<<endl; for(int i=2;i<=n;i++) if(prime[i]==false) cout<<i<<" "; cout<<endl; return 0; } int main(){ int n = 50; sieve_of_eratosthenes(n); return 0; }
Output
Prime numbers between 2 to 50: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
The time complexity of the above algorithm is O(n*log(log n)).