The O(n) Club: Counting Primes That Actually End Before N (and Your Sanity Leaves)

The O(n) Club: Counting Primes That Actually End Before N (and Your Sanity Leaves)

⚡ TL;DR

The real LeetCode ask: count all prime numbers strictly less than n. Brute forcing? Your laptop will start making jet engine noises. Use the Sieve of Eratosthenes — classic, charming, interview-friendly:

// Brute-force (demo purposes only — please avert your eyes):
int count = 0;
for (int i = 2; i < n; i++) if (isPrime(i)) count++;
// Sieve method (your new bestie):
boolean[] isPrime = new boolean[n];
Arrays.fill(isPrime, true);
for (int i = 2; i * i < n; i++)
    if (isPrime[i])
        for (int j = i * i; j < n; j += i)
            isPrime[j] = false;

🧠 How Devs Usually Mess This Up

First-timers either write a new flavor of isPrime() (trial division, so slow cows gossip about you), or shoot themselves in the foot by counting primes up to n inclusive (spoiler: that’s wrong). Oh, and if you start crossing off multiples from i * 2 instead of i * i, you’re doing the Sieve equivalent of double-booking every restaurant table — wasteful and embarrassing.

🔍 What’s Actually Going On

Picture yourself as a bouncer at the exclusive “Numbers Club” (maximum occupancy: n - 1). You let 2 and above in, but as each prime number struts through, you stamp out every one of their multiples — sorry, 4, 6, 8… you’re not on the list. In the end, all the primes are left inside, untouched, and you count them. No brute-force pat-down required.

🛠️ PseudoCode

• Deal with edge cases: If n ≤ 2 — just return 0; there’s nothing to count but regret.
• Set up your club guest list: isPrime[0...n-1] = true;
• Evict the obvious fakers: isPrime[0] = false; isPrime[1] = false;
• Sieve the crowd: For i = 2 to i * i < n:
  • If isPrime[i], for j = i*i to j < n, j += i: mark isPrime[j] = false;
• Tally who’s left: Count isPrime[i] for 2 ≤ i < n.

💻 The Code

public int countPrimes(int n) {
    if (n <= 2) return 0;
    boolean[] isPrime = new boolean[n];
    Arrays.fill(isPrime, true);
    isPrime[0] = false;
    isPrime[1] = false;
    for (int i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    int count = 0;
    for (int i = 2; i < n; i++)
        if (isPrime[i]) count++;
    return count;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Array bounds envy: n is exclusive. Last valid guest: n-1. Don’t be the #offbyone meme.
• The 0/1 are not primes reminder: Don’t waste time discussing existentially with 0 and 1—boot them out fast.
• Avoid double work: Always mark multiples starting at i*i — not i*2, not i+1, or you’re burning CPU for no reason.
• Big O, No Sweat: Even for n ~ 10 million, O(n log log n) is lightning compared to brute force. Space? It’s O(n). Unless your code runs on a potato, you’ll survive.

🧠 Interviewer Brain-Tattoo

“If you’re still brute-forcing primes, at least do it on company time. But really: always sieve like you mean it—your run time (and interviewer) will thank you.”