Sieve of Eratosthenes
A medium Math interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Math
- Sheets
- 3
- Core for
- 13 roles
The problem
List every prime from 2 up to and including n. Use the Sieve of Eratosthenes: start with all numbers marked as candidates and, for each prime you reach, cross out its multiples.
Example 1
- Input
- n = 10
- Output
- [2, 3, 5, 7]
- Why
- The primes up to 10 are 2, 3, 5, and 7. Using the sieve, we eliminate multiples of each prime starting from 2.
Example 2
- Input
- n = 20
- Output
- [2, 3, 5, 7, 11, 13, 17, 19]
- Why
- The primes up to 20 are 2, 3, 5, 7, 11, 13, 17, and 19.
Example 3
- Input
- n = 1
- Output
- []
- Why
- There are no prime numbers less than or equal to 1.
Constraints
- 1 <= n <= 10^6
How to think about it
Updated 2026-09-29Rather than testing every candidate for primality independently, mark composite numbers directly by stepping through multiples of primes already identified. Every composite number must have a prime factor at or below its square root, so crossing off multiples starting from p × p leaves untouched only the prime numbers.
Approaches, worst first
Trial division for each number
time O(n sqrt(n)) · space O(1)
Test each integer k from 2 to n for divisibility up to sqrt(k). The tests are completely independent and waste time re-checking factors across related numbers.
Sieve of EratosthenesWrite this one
time O(n log(log n)) · space O(n)
Allocate a boolean array up to n initialized to true, clear 0 and 1, and for every prime p up to sqrt(n), strike out p × p, p × (p + 1), and so on. Collecting the surviving indices yields all primes up to n.
Where people lose marks · 3
- Starting the inner strike-out loop at 2 × p instead of p × p causes redundant writes, though starting at p × p requires checking for 32-bit integer overflow when p × p exceeds 10^6.
- Treating 0 or 1 as prime when allocating the boolean table; both must be explicitly cleared.
- Off-by-one allocating a table of size n instead of n + 1, causing an out-of-bounds access when evaluating n itself.
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:
Asked at
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 .