# Sieve of Eratosthenes

In this article, we are going to see the state of art Sieve of Eratosthenes which has been there from ancient times and still very helpful concept for solving problems related to Prime numbers.
Submitted by Radib Kar, on March 15, 2019

## 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.

1. Say, we need information up to integer N.
2. Create a table of size N+1, sieve[N+1]
3. Assign all the table entries TRUE initially.
4. Base case:
0 and 1 is not prime
Thus sieve=FALSE=sieve
5. ```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
```
6. Table is built. Now to check any integer K whether prime or not
Return sieve[k]

Example with explanation:

```    Let's say our range is up to 20
Thus initially declare sieve and all are true.
sieve=FALSE
sieve=FALSE
------------------------------------------------------------

sieve=true
Thus all multiple of 2, needed to be false
(Of course they are not prime since divisible by 2)
Thus,
sieve=FALSE
sieve=FALSE
sieve=FALSE
sieve=FALSE
sieve=FALSE
sieve=FALSE
sieve=FALSE
sieve=FALSE
sieve=FALSE
------------------------------------------------------------

sieve=true
Thus all multiple of 3, needed to be false
(Of course they are not prime since divisible by 3)
Thus,
sieve=FALSE (it was already false though)
sieve=FALSE
sieve=FALSE
------------------------------------------------------------

Sieve=FALSE (Nothing to do more with it)
------------------------------------------------------------

sieve=TRUE
Thus all multiple of 5, needed to be false
(Of course they are not prime since divisible by 5)
Thus,
sieve=FALSE (it was already false though)
sieve=FALSE (it was already false though)
sieve=FALSE (it was already false though)

In this way, after completing all possible entries we can find
Only true entries are

sieve
sieve
sieve
sieve
sieve
sieve
sieve
sieve

Others are false.
```

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:

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

int main(){
int n;

cout<<"Enter max range to check for prime numbers\n";
cin>>n;

bool sieve[n+1];

//sieve of eratosthenes
memset(sieve,true,sizeof(sieve));//initially all true
sieve=sieve=false;//0,1 not prime
for(int i=2;i*i<=n;i++)
if(sieve[i])
for(int j=i*2;j<=n;j+=i)//for multiple of i
sieve[j]=false;//can't be prime

cout<<"Enter non-negative integer to check prime or not\n";
cout<<"Negative no to exit\n";

int k;
cin>>k;

while(k>=0){
if(sieve[k])
cout<<k<<" is prime\n";
else
cout<<k<<" is not prime\n";

cout<<"Try more or exit\n";
cin>>k;
}

cout<<"Exited\n";

return 0;
}
```

Output

```Enter max range to check for prime numbers
1000
Enter non-negative integer to check prime or not
Negative no to exit
997
997 is prime
Try more or exit
993
993 is not prime
Try more or exit
13
13 is prime
Try more or exit
103
103 is prime
Try more or exit
111
111 is not prime
Try more or exit
-1
Exited
```

TOP Interview Coding Problems/Challenges

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates