Q:

Sieve of Eratosthenes to find prime numbers using c++

mahmoud2506
Save to bookmark
|
2022-05-05
|
  192 
0

Sieve of Eratosthenes to find prime numbers

C++ programming, examples, C++ programming examples,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-05
need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Most popular and Searched C++ solved programs with Explanation and Output
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
C++ program to print your name randomly on the scr... >>
<< C++ program to print the maximum possible time usi...