Skip to main content

204. Count Primes

mediumAsked at Intel

Count primes strictly less than n. Intel reaches for this in SWE-II rounds because the Sieve of Eratosthenes is a textbook cache-friendly algorithm — sequential memory access, branchless marking, perfect for SIMD. Naive trial-division candidates get filtered out fast.

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

Source citations

Public interview reports confirming this problem appears in Intel loops.

  • Glassdoor (2026-Q1)— Intel SWE-II onsite reports cite count-primes as a recurring algorithms round.
  • GeeksforGeeks (2025-09)— Intel Interview Experience archives reference Sieve of Eratosthenes explicitly.
  • LeetCode discuss (2025-12)— Intel-tagged in the LC company-frequency listing.

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: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Example 2

Input
n = 0
Output
0

Example 3

Input
n = 1
Output
0

Approaches

1. Trial division for each i (brute)

For every i in [2, n), check divisibility by every j in [2, sqrt(i)].

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

Tradeoff: Times out at n ~= 10^6. Useful only as the 'obvious' starting point before the sieve.

2. Sieve of Eratosthenes (optimal)

Allocate a boolean array of length n. For each prime p starting at 2, mark p*p, p*p+p, p*p+2p, ... as composite. Count the unmarked indices.

Time
O(n log log n)
Space
O(n)
function countPrimes(n) {
  if (n <= 2) return 0;
  const isComposite = new Uint8Array(n); // 0 = prime, 1 = composite
  // 0 and 1 are not prime
  isComposite[0] = 1;
  isComposite[1] = 1;
  for (let p = 2; p * p < n; p++) {
    if (isComposite[p] === 0) {
      for (let m = p * p; m < n; m += p) {
        isComposite[m] = 1;
      }
    }
  }
  let count = 0;
  for (let i = 2; i < n; i++) {
    if (isComposite[i] === 0) count++;
  }
  return count;
}

Tradeoff: Near-linear time (log log n grows extremely slowly — it's 4 for n = 10^9). Uses Uint8Array for compact memory; the inner mark loop is a stride access perfect for hardware prefetch.

Intel-specific tips

Intel interviewers grade three things on this problem: (1) you start marking at p*p, not 2*p (everything below p*p was already marked by smaller primes); (2) you use a primitive-typed array like Uint8Array, not a JS array of booleans (4x less memory, better cache behavior); (3) you stop the outer loop at sqrt(n), not n (composites above sqrt(n) are marked by primes below sqrt(n) already). All three are micro-optimizations but together they're the senior-IC signal Intel hunts for.

Common mistakes

  • Marking from 2*p instead of p*p — correct but wastes ~30% of the work.
  • Using `new Array(n).fill(true)` instead of Uint8Array — works but allocates a JS boolean per cell (much larger).
  • Outer loop running to n instead of sqrt(n) — costs an extra O(n) of useless iterations.
  • Off-by-one on the 'strictly less than n' boundary — for n = 10, primes are 2,3,5,7 (count 4), not 2,3,5,7,11.

Follow-up questions

An interviewer at Intel may pivot to one of these next:

  • What if n is so large (10^12) that the sieve array doesn't fit? (Segmented sieve — work in cache-sized chunks.)
  • Generate the nth prime number. (Sieve up to an estimated bound, then index in.)
  • Count primes between L and R for large L, R. (Segmented sieve with primes up to sqrt(R) as the 'crossing-off' set.)
  • What's the parallel sieve algorithm? (Each thread takes a contiguous range; mark by primes < sqrt(n) which a coordinator broadcasts.)

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 marking at p*p?

Any composite c < p*p has at least one prime factor < p (otherwise c would be at least p*p). That prime factor's pass already marked c. So p*p is the first composite that p uniquely contributes to marking.

Why is the runtime O(n log log n)?

The total work is sum over primes p <= n of (n/p). By Mertens' theorem, sum of 1/p over primes <= n is ~log log n. So total marking work is n * log log n.

Could I use a bit-array instead of Uint8Array to save memory?

Yes — pack 8 booleans per byte. Cuts memory 8x, fits ~10^9 primes in ~120MB. The marking loop becomes 2 ops per write (read byte, OR bit, write byte) instead of 1 — slightly slower per write, but you stay in cache for larger n.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →