Faangprep Logo
Log inStart free
Browse curriculum

Sieve of Eratosthenes

The Sieve of Eratosthenes finds all prime numbers up to a specified limit.

UP TO 50 · STOP AT √50 ≈ 7

ASSUME ALL PRIME

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 remove the ones that cannot be. 0 and 1 are out by definition.

Next

2 survived, so it is prime. Start crossing out at 2×2 = 4: anything smaller with a factor of 2 also has a factor below 2 and is already gone.

Limit

50

Intuition

Instead of checking if each number is prime individually (Trial Division), we can iteratively mark the multiples of each prime number as composite. The numbers that remain unmarked are primes.

Concept

  • Idea: Start with 2. Mark all multiples of 2 (4, 6, 8...) as composite. Move to the next unmarked number (3), mark its multiples. Continue until √N.
  • Efficiency: Much faster than Trial Division for finding all primes up to N.
  • Time Complexity: O(N log log N) - very close to linear!

How it Works

Algorithm:

  1. Create a list of booleans up to N, initialized to True.
  2. Set 0 and 1 to False.
  3. Loop p from 2 to √N.
  4. If isPrime[p] is True:
    • Mark all multiples of p (starting from p*p) as False.

Step-by-Step Breakdown

Watch the visualization:

  • Solid blue: The current prime, and the multiple of it being crossed out.
  • Grey, struck through: Multiples already crossed out (composite).
  • Green: Numbers not crossed out yet. Every number still green at the end is prime.

When to Use

  • Generating a list of all primes up to a large number (e.g., 10^7).
  • Pre-computing primes for multiple queries.

When NOT to Use

  • Checking primality for a single very large number (use Miller-Rabin).
  • When memory is very limited (requires O(N) space).

How to Identify

"Find all primes up to N", "Sum of primes", "K-th prime number".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Prime Numbers

Next

Modular Arithmetic

Frequently Asked Questions

Why start marking multiples of p at p*p instead of 2p?

Every smaller multiple of p has a prime factor below p and was already marked when that smaller prime was processed. Starting at p*p skips that repeated work.

Where does O(N log log N) come from?

The sieve performs about N/p writes for each prime p, and the sum of 1/p over the primes up to N grows like log log N. Each composite is touched once per distinct prime factor, not once per candidate divisor.

Sieve or trial division?

Sieve when you need all primes up to N or will answer many primality queries, accepting O(N) memory. Trial division when you need one answer about one number and cannot afford an array of size N.