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.
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
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
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.
Outputneed an explanation for this answer? contact us directly to get an explanation for this answer