Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediummath-number-theory

Count Primes

Problem (restated)

Given an integer n, return how many primes are strictly less than n.

Intuition

Trial-dividing every candidate is O(n √n). The sieve marks composites in bulk: for each prime p, strike multiples starting at p² (smaller multiples were already hit by a smaller prime).

Approaches

Sieve of Eratosthenes

Unverified

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

Idea. Boolean array of size n, 0 and 1 false. For p from 2 while p² < n, if p is still prime, mark p², p²+p, …. Count remaining trues.

Walkthrough. n = 10 → primes 2, 3, 5, 7 → 4. n ≤ 2 → 0.

Trade-offs. Linear space is the cost of the speed. Start crossing at p², not 2p. The answer is primes less than n, so the array is length n, not n+1.

Solution

export function countPrimes(n: number): number {
  if (n <= 2) return 0;
  const prime = new Array<boolean>(n).fill(true);
  prime[0] = false;
  prime[1] = false;
  for (let p = 2; p * p < n; p++) {
    if (!prime[p]) continue;
    for (let m = p * p; m < n; m += p) prime[m] = false;
  }
  let c = 0;
  for (let i = 2; i < n; i++) if (prime[i]) c++;
  return c;
}

export function countPrimes(n: number): number {
  if (n <= 2) return 0;
  const prime = new Array<boolean>(n).fill(true);
  prime[0] = false;
  prime[1] = false;
  for (let p = 2; p * p < n; p++) {
    if (!prime[p]) continue;
    for (let m = p * p; m < n; m += p) prime[m] = false;
  }
  let c = 0;
  for (let i = 2; i < n; i++) if (prime[i]) c++;
  return c;
}

Template connection

Sieve shape of Math & Number Theory: boolean array, cross out from p*p. Off-by-one on “strictly less than n” is the usual trap.

Reflection

0 and 1 are not prime. For each prime p with p * p < n, mark multiples starting at p * p. The answer is how many entries stay unmarked.
Start the crossing at p * p. Smaller multiples were already crossed by an earlier prime.
n <= 2 answers 0. n = 3 answers 1. p * p can overflow a narrow integer.