Understanding the Sieve of Eratosthenes

What is the Sieve of Eratosthenes?

The Sieve of Eratosthenes is a simple and efficient algorithm used to find all prime numbers up to a certain number `n`. It was invented over 2,000 years ago by the Greek mathematician Eratosthenes. Despite its age, it’s still one of the fastest ways to generate a list of primes up to a limit.

How Does It Work?

Imagine you have a list of numbers from 2 to `n`. The Sieve works by eliminating the multiples of each prime number starting from 2.

• Start with a list of numbers from 2 to `n`.
• Pick the first number that hasn’t been marked — it’s a prime.
• Cross out all its multiples.
• Repeat the process with the next number that hasn’t been crossed out.
• Continue until you've processed all numbers up to √`n`.

Result: The numbers that remain unmarked are prime.

Example: Find primes up to 30

Start with this list: [2, 3, 4, 5, 6, ..., 30]

• 2 is prime. Cross out 4, 6, 8, ..., 30.
• 3 is prime. Cross out 6, 9, 12, ..., 30.
• The next uncrossed number is 5. Cross out 10, 15, ..., 30.
• Keep going...

Result: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Code in Java

public class Sieve {
    public static void main(String[] args) {
        int n = 30;
        boolean[] isPrime = new boolean[n + 1];

        // Assume all numbers are prime
        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;
                }
            }
        }

        // Print prime numbers
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                System.out.print(i + " ");
            }
        }
    }
}

Why Is It Efficient?

You eliminate non-primes in batches (multiples). It runs in O(n log log n) time, which is fast for large `n`.

When to Use It

Use the Sieve when:

• You need all prime numbers up to a fixed limit.
• You're solving competitive programming problems related to primes.
• You want to precompute primes for other algorithms (like prime factorization).

Conclusion

That’s it! Simple, fast, and elegant.