Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Cross out composites from each smallest factor: The Prime Sieve.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Sieve of Eratosthenes matches the clues
- 2Keep this true after every move: before base p, every composite below p squared is already marked
- 3Reach the result within O(n log log n) time and O(n) space
Rules and pressure
- Target cost: O(n log log n) time and O(n) space
- State rule: before base p, every composite below p squared is already marked
Lesson 1 of 3
Live algorithm trace
Sieve of Eratosthenes
Complete execution1 of 5
Mark every candidate from two through nine as provisionally prime.
1
prime flags start true from 22
for base while base squared < n3
if base is still prime4
mark multiples from base squared5
count remaining true flags6
return countn = 10candidates = 2..9
Truth to preserve / Cost target
Truth to preserve
before base p, every composite below p squared is already marked
Cost target
O(n log log n) time and O(n) space
Assume every integer from two is prime. For each still-prime base, mark multiples beginning at base squared because smaller multiples already had a smaller factor.
Your call · What should guide every step of this algorithm?