Count Primes
A medium Math interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Math
- Sheets
- 2
- Core for
- 13 roles
The problem
How many primes are there below n? Count the primes that are strictly smaller than n and return that count.
Example 1
- Input
- n = 10
- Output
- 4
- Why
- There are 4 primes less than 10: 2, 3, 5, 7.
Example 2
- Input
- n = 0
- Output
- 0
- Why
- No primes exist below 0.
Example 3
- Input
- n = 1
- Output
- 0
- Why
- No primes exist below 1.
Example 4
- Input
- n = 20
- Output
- 8
- Why
- There are 8 primes less than 20: 2, 3, 5, 7, 11, 13, 17, 19.
Constraints
- 0 <= n <= 5 * 10^6
How to think about it
Updated 2026-09-29The strict upper bound means n itself is never counted, so the sieve needs to span only indices up to n - 1. Because the problem demands a total count rather than the actual list of primes, odd-only indexing cuts memory and strike-out operations by half.
Approaches, worst first
Individual primality checks
time O(n sqrt(n)) · space O(1)
Iterate from 2 up to n - 1 and verify each number with trial division up to its square root. With n up to 5 × 10^6, this performs tens of millions of redundant modulus operations and exceeds typical runtime limits.
Boolean sieve array
time O(n log(log n)) · space O(n)
Maintain a boolean array of length n where is_prime[i] indicates primality. For each prime p up to sqrt(n), mark multiples starting at p × p as composite, then count remaining true values between 2 and n - 1.
Odd-only bitset sieveWrite this one
time O(n log(log n)) · space O(n)
Exclude even numbers from the table completely, tracking only odd candidates 2k + 1. This cuts the space and inner loop iterations by half, making it comfortably pass tight memory limits for n = 5 × 10^6.
Where people lose marks · 3
- Inputs n <= 2 must immediately return 0; allocating or indexing an array of size n without guarding against n = 0 or n = 1 can trigger out-of-bounds errors.
- Counting n itself when n happens to be prime; the statement strictly specifies primes strictly less than n.
- Squaring prime candidate p during the sieve inner loop can exceed 32-bit signed integers when p exceeds 46340, causing integer overflow.
The theory behind it
Math — the ground this problem stands on. All Math problems
What Math is
Algorithmic math is the application of number properties, modular arithmetic, and geometric patterns to compute results without simulating every step. Rather than filling memory buffers with millions of simulated counters or walking endless loops, mathematical formulation uses identities like prime factorization, digit extraction, and greatest common divisors to jump directly to target answers through closed-form rules.
When to reach for it
Reach for mathematical techniques when problem bounds are massive, such as constraints reaching ten to the eighteenth power where simulation is impossible. Strong prompts mention prime generation, greatest common divisor calculations, modular inverses, fast exponentiation, digit reversals, or combinatorial arrangements. If brute-force counting produces memory overflow or time limit exceeded warnings, algebraic reorganization is the intended path.
How the pattern works
Focus on numeric constraints and potential overflows before writing expressions. Break numbers into constituent digits using modulo ten to peel least significant figures and integer division to shrink scale. For divisibility, apply Euclid's remainder theorem repeatedly until remainder drops to zero. Apply modulo arithmetic at every intermediate addition and multiplication stage rather than once at the end, preventing values from spilling beyond standard numeric register limits.
More Math problems
Target Roles
Core requirement for 13 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .