Foundation · Module 2 · Lesson 2
Prime numbers & sieve
Primality testing and Sieve of Eratosthenes.
15–25 min readLesson 8 of 123
Lesson 8 of 123
1d streakTheory lesson · Step-by-step
Understand Prime numbers & sieve
Primality testing and Sieve of Eratosthenes.
Worked approach
Trace the reasoning step by step
- 1Assume every number from 2 through n is prime.
- 2Visit each still-unmarked p through √n.
- 3Mark multiples beginning at p² because smaller multiples were handled earlier.
- 4Collect every index that remains unmarked.
Concrete example
List primes through 20.
- 1Start with 2…20 unmarked.
- 2Mark multiples of 2 from 4.
- 3Mark multiples of 3 from 9.
The remaining values are 2, 3, 5, 7, 11, 13, 17, and 19.
What must remain true (Loop Invariant)
After processing p, every composite with a smallest prime factor at most p is marked.
Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Sieve
O(n log log n)
O(n)
Marks all primes through n.When to use it
- Counting, divisibility, modular cycles, masks, and overflow-safe arithmetic.
- Replacing simulation with a mathematical identity.
- Encoding compact state for search and dynamic programming.
Common mistakes
- Using an identity without checking its domain or overflow behavior.
- Forgetting how the language handles negative remainder and signed shifts.
- Confusing value magnitude with the number of input values.
Practice prompts
- Reproduce the worked Prime numbers & sieve example without looking at the trace.
- Change one input condition and explain whether the Prime numbers & sieve invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check
Can you derive it instead of memorizing it?
State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.