Skip to main content

204. Count Primes

medium

Count the number of primes strictly less than n. The textbook Sieve of Eratosthenes problem — a great test of whether you reach for the right algorithm instead of an O(n * sqrt(n)) primality check per number.

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

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

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Checking each number i from 2 to n-1 with trial division up to sqrt(i) is O(n * sqrt(n)) — too slow for n = 5 * 10^6.

Hint 2

Sieve of Eratosthenes is the right tool. Allocate a boolean array isPrime of length n initialized to true (with 0 and 1 set to false).

Hint 3

For each i from 2 while i * i < n: if isPrime[i], mark every multiple of i starting at i*i as composite (step by i).

Hint 4

Why start at i*i? All smaller multiples (2i, 3i, ..., (i-1)i) were already crossed off by smaller primes.

Solution approach

Reveal approach

Sieve of Eratosthenes. Allocate isPrime[0..n-1] = true, then set isPrime[0] = isPrime[1] = false. For i from 2 while i * i < n: if isPrime[i] is still true, mark isPrime[j] = false for j = i*i, i*i+i, i*i+2i, ... up to n-1. After the sieve, count the indices where isPrime is true. The i*i starting point and the i*i < n bound are the optimizations that take the algorithm from textbook to interview-ready. O(n log log n) time, O(n) space. For n = 5 * 10^6 the sieve runs in well under a second; the per-number primality-test alternative would not.

Complexity

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

Related patterns

  • sieve-of-eratosthenes
  • math

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Apple
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Count Primes and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →