Quick links: C-Tricks HR Interview Que. Code Snippets C Programs C++ Programs Java Programs PHP Examples

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






COMMENTS