Sieve of Eratosthenes
Finds every prime up to n by starting at 2 and crossing out all multiples of each prime, leaving only primes uncrossed. Start crossing at p² since smaller multiples are already gone.
- Category
- Mathematics
- Time complexity
- O(n log log n)
- Space complexity
- O(n)
Pseudocode
mark all numbers prime for p from 2 while p² ≤ n if p still prime, cross out p², p²+p… remaining marks are prime
Reference implementation
prime = [True] * (n+1)
for p in range(2, int(n**0.5)+1):
if prime[p]:
for m in range(p*p, n+1, p):
prime[m] = False