Skip to main content

204. Count Primes

mediumAsked at Goldman Sachs

Count the number of primes less than a non-negative integer n. Goldman Sachs uses Count Primes as a sieve question — the candidate who reaches for the Sieve of Eratosthenes instead of trial-division gets the credit.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Goldman Sachs loops.

  • Glassdoor (2026-Q1)— Goldman Sachs Strats interview reports list Count Primes as a math-flavored quant warm-up.
  • LeetCode Discuss (2025-11)— Count Primes appears in the Goldman Sachs company-tag top-20 problems.

Problem

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

Constraints

  • 0 <= n <= 5 * 10^6

Examples

Example 1

Input
n = 10
Output
4

Explanation: Primes less than 10: 2, 3, 5, 7.

Example 2

Input
n = 0
Output
0

Example 3

Input
n = 1
Output
0

Approaches

1. Trial division per candidate

For each k in [2, n), test if k is prime by trial-dividing up to sqrt(k).

Time
O(n sqrt(n))
Space
O(1)
function countPrimesTrial(n) {
  let count = 0;
  for (let k = 2; k < n; k++) {
    let isPrime = true;
    for (let i = 2; i * i <= k; i++) {
      if (k % i === 0) { isPrime = false; break; }
    }
    if (isPrime) count++;
  }
  return count;
}

Tradeoff: Easy to write and conceptually clear, but blows up well before n = 5 * 10^6. Mention it to show you know primality testing, then move to the sieve.

2. Sieve of Eratosthenes (optimal)

Mark composites in a boolean array. For each prime p starting at 2, mark p*p, p*p+p, p*p+2p, ... as composite.

Time
O(n log log n)
Space
O(n)
function countPrimes(n) {
  if (n < 2) return 0;
  const sieve = new Uint8Array(n);
  let count = 0;
  for (let i = 2; i < n; i++) {
    if (sieve[i] === 0) {
      count++;
      for (let j = i * i; j < n; j += i) {
        sieve[j] = 1;
      }
    }
  }
  return count;
}

Tradeoff: O(n log log n) is essentially linear for any input you'd hit in an interview. Starting the inner loop at i*i (not 2*i) is the small optimization Goldman wants to hear.

Goldman Sachs-specific tips

Goldman Sachs interviewers will let you start with trial division to confirm you understand primality, then explicitly ask for a better approach if n is large. Name the Sieve of Eratosthenes by name — it's a classical algorithm and the interviewer wants the vocabulary. The i*i optimization (start the inner crossing-out at i^2 instead of 2*i) is the small detail that separates 'knows the sieve' from 'wrote it from memory'.

Common mistakes

  • Forgetting to handle n < 2 — both 0 and 1 must return 0.
  • Starting the inner loop at 2*i instead of i*i, which still works but redundantly visits multiples already crossed off by smaller primes.
  • Allocating a boolean array indexed up to n inclusive when the problem asks for primes strictly less than n — off-by-one.

Follow-up questions

An interviewer at Goldman Sachs may pivot to one of these next:

  • Prove the sieve is O(n log log n) — sum of 1/p for primes p ≤ n. (Mertens' second theorem.)
  • How would you generate the actual list of primes, not just the count?
  • Sieve of Atkin gives a slight speedup — when is it worth it? (Almost never for interview-sized inputs; mention it to show breadth.)

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why start the inner loop at i*i?

Any multiple k*i with k < i is k*i = i*k, which was already crossed out when we sieved i with the smaller prime k. So nothing is missed by starting at i*i, and you save work proportional to the sum of (i-2) for each prime i.

Why Uint8Array instead of a regular array of booleans?

Memory locality and constant-factor speed. JS regular arrays are sparse hash maps under the hood; a typed array is a contiguous buffer that the JIT can vectorize. For n = 5 * 10^6 the speedup is large enough to matter in a timed round.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Count Primes and other Goldman Sachs interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →