Primes & Sieve of Eratosthenes

A prime number is an integer greater than 1 whose only divisors are 1 and itself. Primes are the building blocks of all integers — every integer has a unique prime factorization. They appear in hash table sizing, cryptography, and many competitive programming problems.

Checking if a Number Is Prime

The naive approach checks all divisors from 2 to n-1: O(n). The key optimization: if n has a factor larger than √n, it must also have one smaller than √n. So we only need to check up to √n — giving O(√n).

// O(√n) primality check
function isPrime(n: number): boolean {
  if (n < 2) return false;
  if (n < 4) return true;          // 2 and 3 are prime
  if (n % 2 === 0 || n % 3 === 0) return false;
  // All primes > 3 are of the form 6k ± 1
  for (let i = 5; i * i <= n; i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) return false;
  }
  return true;
}

console.log(isPrime(2));    // true
console.log(isPrime(17));   // true
console.log(isPrime(18));   // false
console.log(isPrime(97));   // true  (only 10 iterations for √97 ≈ 9.8)

Note

The 6k±1 pattern works because all primes > 3 leave a remainder of 1 or 5 when divided by 6. Checking only these candidates cuts the iterations by a further 3x compared to checking all odd numbers.

Sieve of Eratosthenes

When you need all primes up to a limit n, the sieve is far more efficient than calling isPrime n times.

Algorithm:

Create a boolean array of size n+1, all set to true.
Start from p=2. For each prime p, mark all multiples of p (starting from p²) as composite.
Repeat until p² > n.

Time complexity: O(n log log n) — nearly linear. Space complexity: O(n).

// Classic Sieve of Eratosthenes
function sieve(n: number): number[] {
  const isPrime = new Uint8Array(n + 1).fill(1);  // 1 = prime
  isPrime[0] = isPrime[1] = 0;

  for (let p = 2; p * p <= n; p++) {
    if (isPrime[p]) {
      // Start from p² — smaller multiples already marked by smaller primes
      for (let multiple = p * p; multiple <= n; multiple += p) {
        isPrime[multiple] = 0;
      }
    }
  }

  const primes: number[] = [];
  for (let i = 2; i <= n; i++) {
    if (isPrime[i]) primes.push(i);
  }
  return primes;
}

const primes = sieve(50);
console.log(primes);
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

// Count primes ≤ n (LeetCode 204)
console.log(sieve(10).length); // 4  (2, 3, 5, 7)

Why Start Marking at p²?

Any composite multiple of p smaller than p² has a prime factor q where q < p. That multiple was already marked when we processed q. Starting at p² avoids redundant work and is the key to the sieve's O(n log log n) complexity — each composite number is marked exactly once.

Segmented Sieve for Large Ranges

When n is huge (e.g., 10^12) the standard sieve needs too much memory. A segmented sieve finds primes in a range [lo, hi] using only O(√hi) memory: first sieve primes up to √hi, then use them to mark composites in the range [lo, hi].

// Segmented sieve for primes in [lo, hi]
function segmentedSieve(lo: number, hi: number): number[] {
  const limit = Math.ceil(Math.sqrt(hi));
  const smallPrimes = sieve(limit);

  // isComposite[i] corresponds to number (lo + i)
  const isComposite = new Uint8Array(hi - lo + 1);

  for (const p of smallPrimes) {
    // First multiple of p that is >= lo
    let start = Math.ceil(lo / p) * p;
    if (start === p) start += p;      // don't mark p itself
    for (let j = start; j <= hi; j += p) {
      isComposite[j - lo] = 1;
    }
  }

  const result: number[] = [];
  for (let i = 0; i <= hi - lo; i++) {
    if (!isComposite[i] && (lo + i) > 1) {
      result.push(lo + i);
    }
  }
  return result;
}

// Primes between 100 and 130
console.log(segmentedSieve(100, 130));
// [101, 103, 107, 109, 113, 127]

Prime Factorization

Every integer > 1 has a unique prime factorization (Fundamental Theorem of Arithmetic). Trial division finds all prime factors in O(√n) by trying each candidate factor.

// Returns prime factors with multiplicity  O(√n)
function primeFactors(n: number): Map<number, number> {
  const factors = new Map<number, number>();

  // Handle factor 2 separately
  while (n % 2 === 0) {
    factors.set(2, (factors.get(2) ?? 0) + 1);
    n /= 2;
  }

  // Check odd factors from 3 to √n
  for (let f = 3; f * f <= n; f += 2) {
    while (n % f === 0) {
      factors.set(f, (factors.get(f) ?? 0) + 1);
      n /= f;
    }
  }

  // If n > 1, it is itself a prime factor
  if (n > 1) factors.set(n, (factors.get(n) ?? 0) + 1);

  return factors;
}

// 360 = 2^3 × 3^2 × 5^1
console.log(primeFactors(360));
// Map { 2 => 3, 3 => 2, 5 => 1 }

// Number of divisors = product of (exponent + 1)
function countDivisors(n: number): number {
  let count = 1;
  for (const exp of primeFactors(n).values()) {
    count *= (exp + 1);
  }
  return count;
}
console.log(countDivisors(360));  // (3+1)(2+1)(1+1) = 24

Smallest Prime Factor Sieve

Precompute the smallest prime factor (SPF) for every number up to n. Then any factorization is O(log n) instead of O(√n), which is essential when you need to factorize many numbers.

// SPF sieve — precompute smallest prime factor
function spfSieve(n: number): number[] {
  const spf = Array.from({ length: n + 1 }, (_, i) => i);  // spf[i] = i initially
  for (let i = 2; i * i <= n; i++) {
    if (spf[i] === i) {  // i is prime
      for (let j = i * i; j <= n; j += i) {
        if (spf[j] === j) spf[j] = i;  // first time we see j — record its SPF
      }
    }
  }
  return spf;
}

// Fast factorization using SPF
function fastFactors(n: number, spf: number[]): number[] {
  const factors: number[] = [];
  while (n > 1) {
    factors.push(spf[n]);
    n = Math.floor(n / spf[n]);
  }
  return factors;
}

const spf = spfSieve(100);
console.log(fastFactors(60, spf));  // [2, 2, 3, 5]

Applications in Algorithms

Application	How primes are used
Hash table sizing	Choose table size as a prime to reduce clustering
Rolling hash (Rabin-Karp)	Use a prime base to minimize hash collisions
RSA cryptography	Security relies on difficulty of factoring large semiprimes
LCM computation	LCM = product of max prime powers across both numbers
Euler totient φ(n)	φ(n) = n × ∏ (1 - 1/p) for each distinct prime p \| n
Counting divisors	Divisors count = ∏ (ei + 1) for prime factorization n = ∏ pi^ei

Count Primes ≤ n (LeetCode 204)

// LeetCode 204 — just use the sieve and count
function countPrimes(n: number): number {
  if (n <= 2) return 0;
  const composite = new Uint8Array(n);
  let count = 0;
  for (let i = 2; i < n; i++) {
    if (!composite[i]) {
      count++;
      for (let j = i * i; j < n; j += i) {
        composite[j] = 1;
      }
    }
  }
  return count;
}

console.log(countPrimes(10));   // 4  (2, 3, 5, 7)
console.log(countPrimes(100));  // 25

Tip

For interview problems, memorize the O(√n) primality check and the basic sieve. Know that the sieve runs in O(n log log n) — nearly linear. If the problem involves many factorizations, reach for the SPF sieve so each factorization is O(log n) rather than O(√n).