MathMathematical Algorithms
Sieve of Eratosthenes
Find every prime up to n by crossing out multiples of each prime starting from its square, in O(n log log n).
2
0
3
1
4
2
5
3
6
4
7
5
8
6
9
7
10
8
11
9
12
10
13
11
14
12
15
13
16
14
17
15
18
16
19
17
20
18
21
19
22
20
23
21
24
22
25
23
26
24
27
25
28
26
29
27
30
28
1/30List every number from 2 to 30, all assumed prime. We only need to sieve with p up to sqrt(30) ≈ 5, because any composite ≤ n has a factor that small.
Current prime pMultiple being crossed outComposite (crossed out)Prime
PseudocodeLearn Sieve of Eratosthenes →
1isPrime = [true] * (n + 1)2for p in 2 .. floor(sqrt(n)):3 if isPrime[p]:4 for m in p*p, p*p+p, .. n:5 isPrime[m] = false6primes = [p for p in 2..n if isPrime[p]]Variables
n30
limit5
Complexity
best O(n)
avg O(n log log n)
worst O(n log log n)
space O(n)
Speed