Home » Algorithms

Find Prime Numbers using Sieve of Eratosthenes Algorithm

In this tutorial, we will learn about the Sieve of Eratosthenes, and how to find prime numbers using this Sieve of Eratosthenes algorithm? By Shubham Singh Rajawat Last updated : August 16, 2023

Problem statement

Write a C++ program to find prime numbers using this Sieve of Eratosthenes algorithm.

Sieve of Eratosthenes algorithm for prime numbers

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/Steps

The steps to find the prime number using Sieve of Eratosthenes algorithm are:

• 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