# sieve of eratosthenes

sieve of eratosthenes is one of oldest and efficient algorithm for generating all prime numbers less than or equal to a given number N. For example if given number is 20 , then all primes less than or equal to 20 would be (2,5,7,11,13,17,19).

## How sieve of eratosthenes works

*To find all the prime numbers less than or equal to 30*.

*List the numbers from 2 to 30.*

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 30

*The first smallest prime is 2, cross out the multiples of 2 except 2. We have colored 2 with blue and crossed out numbers as red*.

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 30

*Now the first number which is still black is 3, so except 3 ,we will crossed out multiples of 3.*

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 30

*Now the first number which is still black is 5, so except 5 ,we will crossed out multiples o*f*5*.

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 30

*Now the next number which is still black is 7, but square root of 30 would be lesser than 7. so at this condition algorithm ends. Now we can print all the elements which has been not crossed out i.e blue and black numbers.**So the primes less than equal to 30 are 2 3 5 7 11 13 17 19 23 29.*

1 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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include<iostream> using namespace std; #define cross 0 #define notcrossed 1 void sieve (int n); void printPrime (int n, bool * prime); int main () { sieve (30); return 0; } void sieve (int n) { // create an bool array of length n + 1 bool *prime = new bool[n + 1]; // make all prime array element not crossed for (int i = 0; i < n + 1; i++) { prime[i] = notcrossed; } for (int i = 2; i * i <= n; i++) { if (prime[i] == notcrossed) { for (int j = i * 2; j <= n; j += i) prime[j] = cross; } } printPrime (n + 1, prime); } void printPrime (int n, bool * prime) { for (int i = 2; i <= n; i++) { if (prime[i] == notcrossed) { cout << i << " "; } } cout << endl; } |

Ref:

http://primes.utm.edu/glossary/xpage/sieveoferatosthenes.html

## Leave a Reply