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 << " ";
}