Medium · Sieve of Eratosthenes
Understand → Visualise → Practice.
Return how many prime numbers are strictly less than `n`.
Assume every number from 2 is prime, then for each prime p cross out its multiples starting at p². What survives is prime.
Create a list of n flags, all true except 0 and 1.
For each p with p × p < n that is still marked, cross out p², p² + p, … below n.
Return how many flags are still true.
O(n log log n) time and O(n) space.
The bound is strictly less than n, so n itself is never counted.
Read the full guide first: Number Theory Basics for Algorithms.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.