Home Â» Technical Interview Questions Â» Algorithm Interview Questions Â» Sieve of Eratosthenes

# Sieve of Eratosthenes

Sieve of Eratosthenes is an algorithm in which we find out the prime numbers less than N. Here N is an integer value. This is an efficient method to find out the prime numbers to a limit. By using this we can find out the prime numbers till 10000000. Here the basic approach is used we just make a memory of size N-1. Store the value continuously from 2 to N in the memory. Now, we traverse from the first unmark number in the memory which is 2. Then, we mark all the multiples of 2 till N. Now we move to the next unmark number in the memory which is 3. Now we mark all the multiples of 3 which are unmarked. Repeat this process until we reach sqrt(N). Here now the unmarked number of our prime number. So, we just iterate one more time and store them in the answer. Let’s see how Sieve of Eratosthenes works.

Table of Contents

## Working Using Example

### Step:1

Create a memory wich containing numbers from 2 to N(Here we take 100).

### Step:2

Mark all the multiples of the first unmark number in the memory which is 2.

### Step:3

Now mark all the multiples next unmarked number which is 3 in the memory.

### Step:4

Move to the next unmark number which is 5. Now mark all the multiples of 5.

### Step:5

Move to the next unmarked number which is our last unmarked number in range 2 to the square root of N.

READ  MiniMax Algorithm

### Step:6

All the remaining unmarked numbers are our prime numbers.

Prime Numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 41, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

## Algorithm

```Step:1 Store the number from 2 to N in the list.
Step:2 Set all numbers as unmarked.
Step:3 For i in range 2 to Sqrt(N):
If i is unmarked then:
Marked all the multiples of i.
Step:4 Print all the unmarked numbers.```

## Implementation

```/*C++ Implementation for Sieve of Eratosthenes.*/
#include<bits/stdc++.h>
using namespace std;
bool marked[1000000];
void Sieve(int n)
{
/*for i from 2 to sqrt(N)*/
for(int i=2;i*i<=n;i++)
{
/*if i is unmarked*/
if(marked[i]==false)
{
/*marked all the multiples of i*/
for(int j=i*i;j<=n;j+=i)
{
/*marked*/
marked[j] = true;
}
}
}
cout<<"Prime number from 2 to N are: "<<endl;
for(int i=2;i<=n;i++)
{
if(marked[i]==false)
{
cout<<i<<" ";
}
}
cout<<endl;
}
int main()
{
/*Take input N*/
int n;
cin>>n;
/*call the sieve function*/
Sieve(n);
return 0;
}```
`100`
```Prime number from 2 to N are:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
```

## Time Complexity

O(N*log(logN)) where N is the limit until we have to find the prime numbers. Here loglogN comes because of the loop run in the following pattern.

For 2 -> It runs N/2 times, For 3 -> It runs N/3 times, For 5 -> It runs N/5 times…

So, N*( 1/2 + 1/3 + 1/5 + 1/7 +……) = N*log(logN).

Note: Harmonic Progression of the sum of primes is equal to the log(logN) where N is the number of terms.

## Space Complexity

O(N) where N is the limit until we have to find the prime numbers. We use this space to store the numbers which we use to mark.

READ  Sliding Window Technique

References

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions Core Java Interview Questions

## AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions Dynamic Programming Questions

# Wait !!!

## You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup