Sieve of Eratosthenes
What is Sieve of Eratosthenes?
Sieve of Eratosthenes is an ancient algorithm of finding prime numbers for any given range. It's actually about maintaining a Boolean table to check for corresponding prime no.
Algorithm
The algorithm is pretty simple.
 Say, we need information up to integer N.
 Create a table of size N+1, sieve[N+1]
 Assign all the table entries TRUE initially.
 Base case:
0 and 1 is not prime
Thus sieve[0]=FALSE=sieve[1]

For(i=2; i*i<=N; i=i+1)
IF(sieve[i] is TRUE) //i is prime
Make all multiple ofi FALSE since they are not prime
sieve[j]=FALSE where j is multiple of i within range N
END IF
END FOR
 Table is built. Now to check any integer K whether prime or not
Return sieve[k]
So now for any given number with in the N
We can tell whether the number is prime or not in O(1) time (based on corresponding TRUE/FALSE value).
When to use this algorithm in programming?
Sieve of Eratosthenes can be very efficient for any program we require to check prime numbers for multiple times (Multiple test cases too).
In such cases, we construct the Sieve of Eratosthenes only single time and for all query each only takes O(1) time reducing the time complexity overall.
C++ implementation:
Output
need an explanation for this answer? contact us directly to get an explanation for this answer