Home » Interview coding problems/challenges

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

- 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]**

**Example with explanation:**

Let's say our range is up to 20 Thus initially declare sieve[21] and all are true. sieve[0]=FALSE sieve[1]=FALSE ------------------------------------------------------------ sieve[2]=true Thus all multiple of 2, needed to be false (Of course they are not prime since divisible by 2) Thus, sieve[4]=FALSE sieve[6]=FALSE sieve[8]=FALSE sieve[10]=FALSE sieve[12]=FALSE sieve[14]=FALSE sieve[16]=FALSE sieve[18]=FALSE sieve[20]=FALSE ------------------------------------------------------------ sieve[3]=true Thus all multiple of 3, needed to be false (Of course they are not prime since divisible by 3) Thus, sieve[6]=FALSE (it was already false though) sieve[9]=FALSE sieve[12]=FALSE(it was already false though) sieve[15]=FALSE sieve[18]=FALSE(it was already false though) ------------------------------------------------------------ Sieve[4]=FALSE (Nothing to do more with it) ------------------------------------------------------------ sieve[5]=TRUE Thus all multiple of 5, needed to be false (Of course they are not prime since divisible by 5) Thus, sieve[10]=FALSE (it was already false though) sieve[15]=FALSE (it was already false though) sieve[20]=FALSE (it was already false though) In this way, after completing all possible entries we can find Only true entries are sieve[2] sieve[3] sieve[5] sieve[7] sieve[11] sieve[13] sieve[17] sieve[19] 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[0]=sieve[1]=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

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions