Sieve of Eratosthenes

Find every prime up to n by crossing out multiples step by step

Beginner
Press Play or Step. Start at 2, the first prime.
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
Primes confirmed
0
Crossed out
0
√N
10.00
Step
0/109
Smallest prime factor
  • 2
  • 3
  • 5
  • 7
current prime prime

How the sieve works

Write down every whole number from 2 to N. The smallest number not yet crossed out is prime, because no smaller prime divides it. Cross out all of its multiples, then move on to the next number that survives. Repeat until you are done: whatever is left standing is prime.

The sieve never tests a number for divisibility. It only adds, jumping through the list in steps of p, which is why it is so fast. Each composite number gets its colour from the first prime that reaches it, which is always its smallest prime factor.

Two shortcuts

Start crossing at p²

first multiple to cross = p × p

Any smaller multiple k·p with k < p has a prime factor smaller than p, so it was already crossed out when that smaller prime was processed. For example, when p = 7 the numbers 14, 21, 28, 35 and 42 are already gone, so the first new one is 49.

Stop once p² > N

sieving primes: p ≤ √N

If a composite n = a × b had both factors greater than √N, then a × b would be greater than N. So every composite up to N has a prime factor at most √N. Once the next prime p satisfies p² > N, there is nothing left to cross out. For N = 100 you only need 2, 3, 5 and 7.

How many primes are there?

The prime counting function π(N) gives the number of primes up to N: π(50) = 15, π(100) = 25, π(150) = 35 and π(200) = 46. The prime number theorem says π(N) is roughly N / ln N, so primes slowly thin out.

How to use this visualizer

  1. 1
    Choose how far to sieve with "Up to N".
  2. 2
    Press Play to animate, or Step to cross out one number at a time. "Next prime" jumps straight to the next sieving prime.
  3. 3
    Watch the dark ring: it marks the number being crossed out right now. Some numbers are visited twice (12 is hit by 2 and by 3), but keep the colour of their smallest prime factor.
  4. 4
    Numbers turn light indigo once they are confirmed prime: anything still standing below p² must be prime.
  5. 5
    At the end, read off π(N) and notice how few sieving primes were needed.

The algorithm in code

Python
def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= n:
        if is_prime[p]:
            for m in range(p * p, n + 1, p):
                is_prime[m] = False
        p += 1
    return [k for k in range(n + 1) if is_prime[k]]

Time complexity

O(N log log N)

The work for prime p is about N / p, and the sum of 1/p over primes up to N grows like log log N.

Space complexity

O(N)

One boolean per number up to N.

Practice problems

Problem 1: Which primes do the work?

You sieve the numbers up to 120. Which primes do you need to cross out multiples of, and how many primes will you find?
Show solution

√120 ≈ 10.95, so only primes ≤ 10 are needed.

Sieving primes: 2, 3, 5, 7 (11² = 121 > 120)

π(100) = 25, plus 101, 103, 107, 109, 113

There are 30 primes up to 120.

Problem 2: Smallest prime factor 7

When sieving up to 100, which numbers get crossed out for the first time while processing p = 7?
Show solution

Multiples of 7 from 7² = 49: 49, 56, 63, 70, 77, 84, 91, 98

56, 70, 84, 98 are even (already crossed by 2)

63 = 3 × 21 (already crossed by 3)

Left: 49 = 7 × 7, 77 = 7 × 11, 91 = 7 × 13

Three numbers: 49, 77 and 91.

Discussion

Questions, ideas or a different approach? Join the conversation.