# Sieve of Eratosthenes Algorithm

Also known as prime number sieves. It’s a famous ancient Math algorithm.

It helps find all the prime numbers ≤ to ‘n’ efficiently.

Prime Sieve Algo Intuition:

1. Idea is to mark all the factors of prime as composite(i.e, non-prime)

2. Step ‘1’ is to be performed for all the primes ≤ sqrt(n).

Step ‘2’ reason is explained in the code below.

void primeSieve(int n) { bool p[n+1]; // prime number memset(p, true, sizeof(p)); // Initialising all values with true // outer loop goes till sqrt(n) because every composite number(i.e, non-prime) has at least one prime factor smaller than or equal to its square root. // Therefore marking factors of prime (upto sqrt(n)) will mark all the composite numbers in the entire range for (int i=2; i*i<=n; i++) { if (p[i] == true) // mark its multiple as non-prime { for (int j=i*i; j<=n; j += i) p[j] = false; } } // Print all prime numbers for (int i=2; i<=n; i++) if (p[i]) cout << i << " "; }