Problem Description

• LeetCode 204 Count Primes

Given an integer n, return the number of prime numbers that are less than n. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. For example, if n = 10, the prime numbers less than 10 are [2, 3, 5, 7], so the answer is 4.

Core Algorithm Walkthrough

The Sieve of Eratosthenes is an ancient algorithm (circa 240 BC) that efficiently finds all prime numbers up to a given limit. The key insight is that instead of checking each number individually for primality, we can eliminate all multiples of known primes.

The Algorithm Steps:

1. Create a boolean array where isPrime[i] represents whether number i is prime
2. Initialize all values to true (assume all numbers are prime initially)
3. Mark 0 and 1 as not prime (by definition)
4. Starting from 2, for each prime number p:
   • Mark all multiples of p (starting from p²) as composite (not prime)
   • Move to the next unmarked number
5. Count all remaining true values

Key Optimizations:

• Start marking from p²: All smaller multiples of p have already been marked by smaller primes
• Only iterate up to √n: Any composite number greater than √n must have a prime factor less than √n
• Skip even numbers: After handling 2, we can skip all even numbers since they're composite

Why It Works: The fundamental theorem is that every composite number has a prime factor ≤ √n. By systematically eliminating multiples of each prime, we're left with only prime numbers.

Complexity Analysis

Time Complexity: O(n log n)

• The algorithm visits each number at most once for each of its prime factors
• The harmonic series of primes gives us the log n factor
• Much more efficient than checking each number individually O(n√n)

Space Complexity: O(n)

• We need a boolean array of size n to track prime status

Full Solution (Java)

class Solution {
    public int countPrimes(int n) {
        // Handle edge cases
        if (n <= 2) return 0;

        // Create boolean array - isPrime[i] represents if number i is prime
        boolean[] isPrime = new boolean[n];

        // Initialize all numbers as prime (except 0 and 1)
        for (int i = 2; i < n; i++) {
            isPrime[i] = true;
        }

        // Sieve of Eratosthenes
        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                // Mark all multiples of i starting from i*i as composite
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        // Count remaining primes
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                count++;
            }
        }

        return count;
    }
}

Step-by-Step Example

Let's trace through the algorithm for n = 10:

Initial Setup:

Index:   0  1  2  3  4  5  6  7  8  9
isPrime: F  F  T  T  T  T  T  T  T  T

i = 2 (first prime):

• Mark multiples of 2 starting from 2² = 4: {4, 6, 8}

  Index:   0  1  2  3  4  5  6  7  8  9
  isPrime: F  F  T  T  F  T  F  T  F  T
  

i = 3 (next prime):

• Mark multiples of 3 starting from 3² = 9: {9}

  Index:   0  1  2  3  4  5  6  7  8  9
  isPrime: F  F  T  T  F  T  F  T  F  F
  

i = 4: Already marked as composite, skip

Loop ends when i² ≥ n (4² = 16 ≥ 10)

Final Count: Numbers with isPrime[i] = true: {2, 3, 5, 7} = 4 primes

Code Breakdown

1. Edge Case Handling:

if (n <= 2) return 0;

• No primes exist below 2

2. Array Initialization:

boolean[] isPrime = new boolean[n];
for (int i = 2; i < n; i++) {
    isPrime[i] = true;
}

• Create array with indices 0 to n-1
• Mark all numbers ≥ 2 as potentially prime

3. Sieving Process:

for (int i = 2; i * i < n; i++) {
    if (isPrime[i]) {
        for (int j = i * i; j < n; j += i) {
            isPrime[j] = false;
        }
    }
}

• Outer loop: Check each potential prime up to √n
• Inner loop: Mark all multiples starting from i²

4. Counting:

int count = 0;
for (int i = 2; i < n; i++) {
    if (isPrime[i]) count++;
}

• Count all remaining unmarked numbers

Alternative Optimized Version

For even better performance, we can optimize by handling even numbers separately:

class Solution {
    public int countPrimes(int n) {
        if (n <= 2) return 0;
        if (n == 3) return 1; // Only prime 2

        boolean[] isPrime = new boolean[n];
        int count = 1; // Count 2 as prime

        // Only check odd numbers
        for (int i = 3; i < n; i += 2) {
            isPrime[i] = true;
        }

        // Sieve only odd numbers
        for (int i = 3; i * i < n; i += 2) {
            if (isPrime[i]) {
                for (int j = i * i; j < n; j += 2 * i) {
                    isPrime[j] = false;
                }
            }
        }

        // Count odd primes
        for (int i = 3; i < n; i += 2) {
            if (isPrime[i]) count++;
        }

        return count;
    }
}

The Sieve of Eratosthenes demonstrates how ancient mathematical insights can lead to highly efficient modern algorithms, transforming a potentially expensive primality testing problem into an elegant marking process.