Prime Numbers

Concept

LeetCode #204.
Problem: Given an integer n, return the number of prime numbers that are strictly less than n.

A Prime Number is a number greater than 1 that cannot be formed by multiplying two smaller natural numbers. (e.g., 2, 3, 5, 7, 11).

The Naive Approach ($O(N^2)$)

To check if a number X is prime, you could just loop from 2 up to X - 1. If X % i === 0, it’s not prime!
To count all primes up to N, you would loop X from 2 to N, and run that inner loop every single time.
This is $O(N^2)$ and will trigger a Time Limit Exceeded error.

Optimization 1 ($O(N √N)$):
You don’t need to check up to X - 1. You only need to check up to $O(√X)$.
Why? Because factors mathematically exist in pairs! For 36, the factors are (2, 18), (3, 12), (4, 9), (6, 6).
Once you cross the square root (6), the pairs just reverse! (9, 4), (12, 3). If you haven’t found a factor by the time you hit the square root, it is mathematically impossible to find one later. The number is guaranteed to be prime!

The Optimal Approach: Sieve of Eratosthenes

Instead of checking if every individual number is prime, we use an ancient Greek algorithm that filters them out in massive batches.

1. Create a boolean array of size N, initialized entirely to true.
2. Start at 2 (the first prime). 2 is true!
3. Because 2 is prime, we know that ANY multiple of 2 is mathematically NOT prime!
4. We run an inner loop that instantly crosses out 4, 6, 8, 10... marking them as false.
5. We move to 3. It is true! We instantly cross out 6, 9, 12, 15....
6. We move to 4. It was already crossed out by 2! We safely skip it.
7. By the time we finish, the only numbers still marked true are the mathematically pure primes!

Implementation

// Time Complexity: O(N * log(log N)) (Functionally indistinguishable from O(N))
// Space Complexity: O(N) (The boolean array)

function countPrimes(n: number): number {
    // There are no primes strictly less than 2
    if (n <= 2) return 0;

    // Create the boolean sieve
    const isPrime = new Array(n).fill(true);
    
    // 0 and 1 are mathematically not prime
    isPrime[0] = false;
    isPrime[1] = false;

    // We only need to run the sieve up to the square root of N!
    // Why? Because any multiple larger than sqrt(N) was ALREADY crossed out 
    // by a smaller prime factor earlier in the loop!
    const limit = Math.sqrt(n);
    for (let i = 2; i <= limit; i++) {
        
        // If the current number is still marked as Prime...
        if (isPrime[i] === true) {
            
            // Cross out ALL of its multiples!
            // Optimization: We can start crossing out at i * i.
            // (e.g., if i is 5, we don't need to cross out 10 or 15, because 
            // the 2 and 3 loops already crossed them out! We start at 25).
            for (let multiple = i * i; multiple < n; multiple += i) {
                isPrime[multiple] = false;
            }
        }
    }

    // Finally, just count how many 'true's survived!
    let primeCount = 0;
    for (let i = 2; i < n; i++) {
        if (isPrime[i] === true) primeCount++;
    }

    return primeCount;
}

Interview Questions

Q: In the Sieve, why do we start the inner loop at i * i?
A: This is a legendary optimization. Let’s say i is 7.
You could start crossing out at 7 * 2 = 14. Then 7 * 3 = 21. Then 7 * 4 = 28.
But think about it: 14 was already crossed out when i was 2. 21 was already crossed out when i was 3. 28 was already crossed out when i was 2 (and 4).
Every multiple smaller than 7 * 7 is mathematically guaranteed to contain a smaller prime factor that has already run its course! The absolute first “brand new” multiple that 7 is responsible for crossing out is 7 * 7 = 49.

Q: Is 1 a prime number?
A: No. By mathematical definition, a prime number must have exactly two distinct positive divisors: 1 and the number itself. The number 1 only has a single divisor (1). Therefore, 0 and 1 are never prime.