C C++ Java Data Structure Python JavaScript CSS Ajax PL/SQL PHP Puzzles C programs C++ programs Java programs

Home » Algorithms

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.

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.

#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

Liked this article? Do share with your friends :)

C, C++, Java, D.S., Python, .Net, SQL, PL/SQL, Ajax, PHP, JavaScript, CSS, HTML, C programs, C++ programs, Java programs, C# programs, DS programs, C aptitude, C++ aptitude, Java aptitude, DBMS aptitude, O.S., Networking, Embedded systems, Nanotechnologies, Linux, DOS, puzzles, syntaxes,