bool isPrime[n+1];
for (int i = 2; i <= n; i++) isPrime[i] = true;
for (int p = 2; p * p <= n; p++) {
    if (isPrime[p]) {
        for (int i = p * p; i <= n; i += p)
            isPrime[i] = false;
    }
}

1. What Is The Sieve Of Eratosthenes?

The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. It works by iteratively marking the multiples of each prime number starting from 2, leaving only the prime numbers unmarked.

2. How Does The Algorithm Work?

The Sieve of Eratosthenes follows these steps:

1. Create a boolean array isPrime[0..n] and initialize all entries as true
2. Mark isPrime[0] and isPrime[1] as false (not prime numbers)
3. Start from p = 2, the first prime number
4. Mark all multiples of p greater than or equal to p² as false
5. Find the next number greater than p that is marked true - this is next prime
6. Repeat steps 4-5 until p² > n

Time Complexity: O(n log log n)
Space Complexity: O(n)

3. C++ Implementation Details

Complete C++ Code:

#include <iostream>
#include <vector>
using namespace std;

vector<int> sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n + 1, true);
    vector<int> primes;
    
    isPrime[0] = isPrime[1] = false;
    
    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }
    
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }
    
    return primes;
}

int main() {
    int n;
    cout << "Enter n: ";
    cin >> n;
    
    vector<int> primes = sieveOfEratosthenes(n);
    
    cout << "Prime numbers up to " << n << ":\n";
    for (int prime : primes) {
        cout << prime << " ";
    }
    
    return 0;
}

4. Using The Prime Calculator

Instructions: Enter a positive integer n (2 ≤ n ≤ 100,000) to find all prime numbers up to n using the Sieve of Eratosthenes algorithm.

5. Frequently Asked Questions (FAQ)

Q1: Why start marking multiples from p² instead of 2p?
A: All smaller multiples of p (2p, 3p, ..., (p-1)p) would have already been marked by smaller primes, making p² the first unmarked multiple.

Q2: What is the time complexity of this algorithm?
A: O(n log log n), which is nearly linear and very efficient for finding primes up to large numbers.

Q3: How does this compare to trial division?
A: Much more efficient. Trial division has O(n√n) time complexity, while Sieve of Eratosthenes is O(n log log n).

Q4: What are the limitations of this method?
A: Requires O(n) memory space, which can be problematic for very large n (billions). For extremely large ranges, segmented sieve is preferred.

Q5: Can this algorithm be optimized further?
A: Yes, by skipping even numbers (except 2), using bit-level operations for memory efficiency, or implementing segmented sieve for large ranges.