Count Primes

medium math enumeration

Problem

Given an integer n, return the number of prime numbers strictly less than n.

Inputn = 10

Output4

Primes < 10: 2, 3, 5, 7 → count = 4. Sieve of Eratosthenes: for each prime p in [2 .. √n], mark p², p²+p, … as composite.

n (2–50)

def count_primes(n):
    if n <= 2: return 0
    sieve = [True] * n
    sieve[0] = sieve[1] = False
    for p in range(2, int(n ** 0.5) + 1):
        if sieve[p]:
            for m in range(p * p, n, p):
                sieve[m] = False
    return sum(sieve)

function countPrimes(n) {
  if (n <= 2) return 0;
  const sieve = new Uint8Array(n).fill(1);
  sieve[0] = sieve[1] = 0;
  for (let p = 2; p * p < n; p++) {
    if (sieve[p]) for (let m = p * p; m < n; m += p) sieve[m] = 0;
  }
  let count = 0;
  for (let i = 2; i < n; i++) if (sieve[i]) count++;
  return count;
}

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

int countPrimes(int n) {
    if (n <= 2) return 0;
    vector<bool> sieve(n, true);
    sieve[0] = sieve[1] = false;
    for (int p = 2; p * p < n; p++)
        if (sieve[p]) for (int m = p * p; m < n; m += p) sieve[m] = false;
    int count = 0;
    for (int i = 2; i < n; i++) if (sieve[i]) count++;
    return count;
}

Explanation

To count primes below n quickly, we use the classic Sieve of Eratosthenes: instead of testing each number for primality, we cross out all the multiples of every prime we find.

We make a boolean array sieve where every index starts marked True (assume prime), then set sieve[0] and sieve[1] to False since 0 and 1 are not prime. Walking p from 2 upward, whenever sieve[p] is still True, p is prime, so we mark all its multiples as composite.

Two speed tricks: we only loop p up to √n (any larger composite already got crossed out by a smaller factor), and we start crossing out at p * p because smaller multiples like 2p, 3p were already handled by earlier primes.

Example with n = 10: start at p = 2, cross out 4, 6, 8. Then p = 3, cross out 9. p stops there since 4 × 4 > 10. The survivors 2, 3, 5, 7 are the primes, so the count is 4.

At the end we simply sum the still-True entries. Crossing out multiples is far cheaper than testing each number, giving the near-linear O(n log log n) running time.

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