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 Sam K., 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.

More Intel coding interview questions

See all Intel problems →

Companies that also ask Count Primes