Generation
# Sieve of Eratosthenes
**Definition:** An ancient algorithm for finding all prime numbers up to a given limit by iteratively marking the multiples of each prime as composite.
## How it works:
1. List all numbers from 2 to n
2. Start with the first unmarked number (it's prime)
3. Mark all its multiples as composite
4. Repeat with the next unmarked number
5. Continue until you've processed all numbers
## Worked Example: Find all primes up to 30
**Initial list:** 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
**Step 1:** 2 is prime. Cross out multiples of 2:
- 2, 3, ~~4~~, 5, ~~6~~, 7, ~~8~~, 9, ~~10~~, 11, ~~12~~, 13, ~~14~~, 15, ~~16~~, 17, ~~18~~, 19, ~~20~~, 21, ~~22~~, 23, ~~24~~, 25, ~~26~~, 27, ~~28~~, 29, ~~30~~
**Step 2:** 3 is prime. Cross out multiples of 3:
- 2, 3, 5, 7, ~~9~~, 11, 13, ~~15~~, 17, 19, ~~21~~, 23, 25, ~~27~~, 29
**Step 3:** 5 is prime. Cross out multiples of 5:
- 2, 3, 5, 7, 11, 13, 17, 19, 23, ~~25~~, 29
**Step 4:** 7 is prime, but 7² = 49 > 30, so we're done!
**Primes up to 30:** 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
25 tokens in · 547 tokens out · 7019 ms · $0.0083