← DSA Atlas
Dedicated problem page · #204

Count Primes

MediumRandomization, Math and Miscellaneous (FAANG add-on)Sieve of EratosthenesBoolean sieve array
Solve on LeetCode ↗
204
MediumRandomization, Math and Miscellaneous (FAANG add-on)Boolean sieve arraySieve of Eratosthenes

Count Primes

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

Open official problem prompt ↗
In plain English

Count how many primes lie below a possibly very large bound n, fast enough for n up to five million.

Picture it like this

Standing at each prime and crossing off every one of its multiples on a numbered list, like striking out every second, third, fifth seat in a stadium.

Example
Input
n = 10
Output
4
Why
The primes strictly below 10 are 2, 3, 5, and 7, which is 4 primes.
Constraints
0 <= n <= 5 * 10^6
Pattern lesson

See the pattern, then code

Sieve of Eratosthenes
Recognition clue

Counting all primes below a large bound is the textbook cue for the Sieve of Eratosthenes rather than testing each number individually.

↗
Randomization, Math and Miscellaneous (FAANG add-on)

Uniform random selection, sampling streams, number theory, or precision-heavy parsing.. Every composite has a prime factor no larger than its square root, so marking multiples of each prime starting at its square eliminates all composites efficiently.

New words, made simpleKnow these before the algorithm
Sieve
A boolean array where index p records whether p is still considered prime.
Composite
A number with a divisor other than 1 and itself; every composite gets crossed out.
Square-root bound
Only primes up to sqrt(n) need to start crossing out multiples.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Trial division per number

Far too slow at n = 5*10^6.

Test each k below n for divisibility up to sqrt(k).

Time O(n sqrt(n))Space O(1)
Best choiceSieve of Eratosthenes

Near-linear and the standard efficient method.

Cross out multiples of each prime starting from its square.

Time O(n log log n)Space O(n)
The rule we keep true

Invariant

When the outer loop reaches index i, every composite with a prime factor smaller than i has already been marked False, so if sieve[i] is still True then i is prime.

Why this is correct

Reasoning

Any composite c has a smallest prime factor p <= sqrt(c) <= sqrt(n), and when the loop processes p it marks c; starting at i*i is safe because smaller multiples of i were already crossed out by smaller primes.

The algorithm in three movesSay these aloud before coding
1Return 0 immediately for n < 3

sieve size 10, cross out 4,6,8 (mult of 2)

2Create a boolean array of size n, marking 0 and 1 as non-prime

cross out 9 (mult of 3)

3For each i up to sqrt(n) that is still prime, mark multiples i*i, i*i+i, ... as composite

remaining primes 2,3,5,7 -> count 4

4Count the remaining True entries

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
20
31
42
53
64
75
86
97
1 · Readn = 10
2 · AskTrivially empty?
3 · Update staten >= 3
4 · ResultProceed with sieve of size 10.
Key takeaway

Numbers below 10 with primes 2,3,5,7 highlighted after sieving.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Edge guard

    For n < 3 there are no primes below n.

  2. 2
    Lines 5-6Initialize

    All True except 0 and 1, which are not prime.

  3. 3
    Lines 7-10Cross out multiples

    Only iterate i to sqrt(n); start marking at i*i to skip already-marked multiples.

  4. 4
    Lines 11Tally

    Summing the boolean array counts the surviving primes.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • n = 0 or 1 -> 0
  • n = 2 -> 0 (no prime strictly less than 2)
  • n = 3 -> 1 (only 2)
  • Large n near 5*10^6 must complete in time via the sieve
!

Common beginner mistakes

  • Counting primes up to n inclusive instead of strictly less than n
  • Starting inner marking at 2*i instead of i*i (correct but slower) or at i (wrong)
  • Iterating i to n instead of sqrt(n), wasting time
  • Marking 0 and 1 as prime
Check your understanding

Why can multiples start at i*i rather than 2*i?

More in Randomization, Math and Miscellaneous (FAANG add-on)

#43Multiply StringsSchoolbook grid multiplication#68Text JustificationGreedy line packing with space distribution#166Fraction to Recurring DecimalLong division with remainder cycle detection#273Integer to English WordsChunk-by-thousands decomposition#382Linked List Random NodeReservoir sampling (size 1)#384Shuffle an ArrayFisher-Yates shuffle