// NUMBER THEORY · BEGINNER

Sieve of Eratosthenes

The most ancient and elegant way to catch all prime numbers in a range — one simple rule: cross out the multiples.

Start Sieving Play Sieve Sweep
Beginner·12 min·Mathematics · Number Theory
Reviewed by CodeTikki Academic Team

Prerequisites: Multiplication tables · Prime vs composite

// VISUALIZER

Catch the primes one multiple at a time

Change the limit n and press play. The sieve starts with 2, then 3, then 5 — each time crossing out all multiples of the current 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

Press PLAY to watch the Sieve of Eratosthenes mark non-prime numbers.

Step

0 / 77

Primes Found

0

Crossed

0

// MINI GAME

Sieve Sweep

Beat the clock and cross out every multiple of the current prime. Miss one or click a non-multiple and your streak resets.

Sieve Sweep

Click all the multiples of the current prime before the timer runs out.

// FLOWCHART

Algorithm flow

// FLOWCHART · Sieve of Eratosthenes
Find all primes up to n
YesNoDoneStartisPrime[2..n] = truefor p = 2 to nisPrime[p]?for m = 2p to n step pisPrime[m] = falsereturn all p where isPrime[p]End

Press PLAY to trace the algorithm through the flowchart.

0 / 8

// PSEUDOCODE

Trace the code

// PSEUDOCODE · Sieve of Eratosthenes
Find primes up to n = 20
n = 20
1function sieveOfEratosthenes(n):
2 isPrime[1..n] = true
3 for p = 2 to n:
4 if isPrime[p]:
5 for m = 2*p to n step p:
6 isPrime[m] = false
7 return all p where isPrime[p]

Press PLAY to step through the algorithm line by line.

0 / 17

// TUTORIAL QUIZZES

Test your mastery

Three progressive quizzes. Prove you can sieve, understand the complexity, and name the variants.

// PRACTICE & ASSESS

Test your understanding

Now that you've learned the concept, put it into practice. Solve coding problems and take quizzes to reinforce what you've learned.

💻

Coding Problems

The Sieve Master: Find All Primes Up to NL2The Segmented Sieve: Primes in a Large RangeL6The Prime Counter: Count Primes Up to NL4The Smallest Prime Factor TableL4The Linear Sieve: Euler SieveL7

// REFERENCES

Sources & further reading

  1. [1]
    Sieve of EratosthenesEratosthenes of Cyrene (~240 BC)
  2. [2]
    Introduction to Algorithms (CLRS)T. H. Cormen et al. — Number-theoretic algorithms
  3. [3]
    The Art of Computer Programming, Vol. 2Donald Knuth — Section 4.5.4: factoring into primes
  4. [4]
    Prime Numbers and Computer Methods for FactorizationHans Riesel — sieve methods and algorithms

// READY?

Break numbers into their building blocks

Next up: Prime Factorization. Learn how to break any number into its unique product of primes.

Prime Factorization GCD & Euclidean