# Sieve of Eratosthenes in C++

In this tutorial, we learn about sieve of Eratosthenes algorithm in C++.
Before we start, let’s know about what is sieve of Eratosthenes algorithm?

sieve of Eratosthenes algorithm is a very famous and efficient algorithm to generate all small prime numbers up to around 1-10 million. This algorithm is given by a Greek mathematician named Eratosthenes.  By using this algorithm, we can write a simple program for prime number generation.

What we do in this particular algorithm is that, we first create a list of all the numbers from 2 to n and initially say that all of them are prime.

If n=25,
We create a list from 2 to 20

`2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20.`

Now we start the first element in the list, if 2 is prime, all the multiples of 2 can’t be prime. We cancel all the multiples of 2, they are not prime because they are divided by 2.

`2  3  5  7  9  11  13  15  17  19.`

Now we go to 3, so all the multiples of 3 can’t be prime, so they cancel out.

`2  3  5  7  11  13  17  19.`

All the remaining numbers are prime. So this is how sieve of Eratosthenes algorithm works.

## C++ Program: sieve of Eratosthenes in C++

```#include <iostream>
const int n = 20;

int main()
{
int arr = {0};

for (int i = 2; i < 20; i++)
{
for (int j = i * i; j < 20; j+=i)
{
arr[j - 1] = 1;
}
}
for (int i = 1; i < 20; i++)
{
if (arr[i - 1] == 0)
std::cout << i << "\t";
}
}```

`Output:  1    2    3    5    7    11    13    17    19.`

Do let me know in the comment section if you have any doubt.

Check if a number is an Armstrong number or not in C++