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.

Prime Sieves Algo Visualisation
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 << " "; 

You might also like to check the following articles: