Home »
Algorithms

# Sieve of Eratosthenes to find prime numbers

Learn: What is **Sieve of Eratosthenes**? And how to **find prime numbers using this algorithm**? This article contain solved program in C++ based on Sieve of Eratosthenes algorithm.

Submitted by Shubham Singh Rajawat, on August 08, 2017

**Sieve of Eratosthenes is an algorithm for finding all the prime numbers up to any given number.**

It works on a very simple logic of iteratively marking every composite (non-prime) starting from 2. It is done by marking multiple of 2 and then chooses the next greatest numbers which is not marked and mark its multiple and so on.

## Algorithm

**Step 1:** let i=2, the smallest prime number
**Step 2:** mark all multiple of āiā i.e. 2i,3i,4i,... as non-prime
**Step 2:** find the next greatest number which is not marked
and update value of āiā to the number chosen
**Step 3:** repeat step 2
**Step 4:** all the numbers that are not marked are prime numbers.

### C++ program to find prime numbers using Sieve of Eratosthenes algorithm

#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n;
cout<<"Enter the number: ";
cin>>n;
vector<int> prime(n+1,1);
for(int i=2;i*i<=n;i++)
{
if(prime[i]==1)
{
for(int j=i;i*j<=n;j++)
{
prime[i*j]=0;
}
}
}
cout<<"Prime number upto "<<n<<" are: ";
for(unsigned i=2;i<=prime.size();i++)
{
if(prime[i]==1)
{
cout<<i<<" ";
}
}
cout<<endl;
return 0;
}

Output

First Input:
Enter the number: 100
Prime number upto 100 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
Second Input:
Enter the number: 200
Prime number upto 200 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 101 103 107 109 113 127 131 137
139 149 151 157 163 167 173 179 181 191 193 197 199

Sponsored Links