# Sieve of Eratosthenes

Sieve of Eratosthenes is a technique formulated by a brilliant Greek mathematician, Eratosthenes, whose efforts greatly contributed to identifying prime numbers.

He contributed a lot to mathematics, and the discovery of sieve was the best he had done in this field. It is a pattern or algorithm that works by eliminating numbers that do not fit in a scenario.

**Algorithm :**

- List all consecutive numbers from 2 to η, i.e. (2, 3, 4, 5, ……, η).
- Assign the first prime number-letter
*p*. - Beginning with
*p*2, perform an incremental of*p*and mark the integers equal or greater than*p*2 in the algorithm. These integers will be*p*(*p*+ 1),*p*(p + 2),*p*(*p*+ 3),*p*(*p*+ 4) … - The first unmarked number greater than
*p*is identified from the list. If the number does not exist in the list, the procedure is halted.*p*is equated to the number and step 3 is repeated. - The Sieve of Eratosthenes is stopped when the square of the number being tested exceeds the last number on the list.
- All numbers in the list left unmarked when the algorithm ends are referred to as prime numbers.

*Let us take an example to understand more clearly*

if n=30 we need to print prime numbers smaller than or equal to 30 in an efficient way.

*Step 1:*The first step is to list all the numbers.

2, 3, 4, 5, 6 ,7 ,8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, and 30.

*Step 2:*Write in**bold**all multiples of 2, except 2 itself.

2, 3, **4**, 5, **6** , 7 , **8**, 9, **10**,11, **12**, 13, **14**, 15, **16**, 17, **18**, 19, **20**, 21, **22**, 23, **24**, 25, **26**, 27, **28**, 29, and **30**.

*Step 3:*The next unshaded number is 3. Write its square (32 = 9) in bold.

2, 3, **4**, 5, **6** , 7 , **8**, **9**, **10**,11, **12**, 13, **14**, **15**, **16**, 17, **18**, 19, **20**, **21**, **22**, 23, **24**, 25, **26**, **27**, **28**, 29, and **30**.

*Step 4:*Now the third unshaded number is 5. Write its square 52=25 in bold.

2, 3, **4**, 5, **6** , 7 , **8**, **9**, **10**,11, **12**, 13, **14**, **15**, **16**, 17, **18**, 19, **20**, **21**, **22**, 23, **24**, **25**, **26**, **27**, **28**, 29, and **30**.

*Step 5:*The fourth unshaded number is 7 and more than the square root of 30. Therefore, there are no multiples of 7 left since they have been eliminated by 2 and 3 as 14, 28, and 21 respectively. The remaining numbers 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29 are prime.

**C++ implementation of the above approach**

#include <bits/stdc++.h>

#define ll long long int

using namespace std;

void SieveOfEratosthenes(ll n)

{

bool prime[n+1];

memset(prime, true, sizeof(prime));

for (ll p=2; p*p<=n; p++)

{

if (prime[p] == true)

{

for (ll i=p*p; i<=n; i += p)

prime[i] = false;

}

}

for (ll p=2; p<=n; p++)

if (prime[p])

cout << p << “ “;

}

int main(){

ll n;cin>>n;

SieveOfEratosthenes(n);

return 0;

}

**INPUT- **100

**OUTPUT- **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

**Time complexity: O(n*log(log(n))**