Sieve of Eratosthenes
Visualize primes up to N.
30 primes ≤ 120
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
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
All primes up to 120
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113
Sieve of Eratosthenes (c. 200 BCE). Mark all multiples of each prime as composite. What's left is the primes. Still the fastest practical algorithm for finding all primes below ~10⁹.
About
Pick a number up to 1000. The tool runs the classical sieve and shows the grid with primes highlighted. Lists all primes in the range.
How to use
- Pick an upper bound.
FAQ
Is this fast?+
For N below 10⁹, yes. The sieve runs in O(N log log N). For larger ranges, segmented sieves or wheel factorization are faster.