Sieve of Eratosthenes
Mark multiples to generate primes up to N in O(n log log n).
mathprimessieveUpdated 2025-09-01
Steps
- Assume all prime
- Start p=2, mark multiples p*p..
- Next unmarked
Complexity
- Time O(n log log n)
- Space O(n)
Mark multiples to generate primes up to N in O(n log log n).