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

More Math practice problems

See all Math problems →