Sieve of Eratosthenes
MediumWalk the numbers. The first unmarked number is prime, and all of its multiples are not. Start marking from its square.
number theorymarking multiples
TimeO(n log log n)
SpaceO(n)
InputAn upper bound up to 100
0
1
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
Assume every number from 2 to 50 is prime, then eliminate.
1 / 53
isPrime[2..n] = true
for p from 2 while p*p <= n:
if isPrime[p]:
for m from p*p to n step p:
isPrime[m] = false
Why it matters
Starting from p squared is safe because smaller multiples already carry a smaller prime factor.
Practise this
Keyboard
space play← → stepr restartctrl K search
Next visualiser
Binary Search