{ }SolveLogs
⌕
Home / Maths / GFG
GeeksforGeeks Medium

Sieve of Eratosthenes

Sieve of Eratosthenes is a GFG problem. Given an integer n, return every prime number from 1 to n (inclusive), in increasing order.

  • A prime is an integer greater than 1 whose only divisors are 1 and itself.
  • 1 is not prime, so for n < 2 the answer is an empty list.
  • n can be 10⁶. Testing each number for divisors up to its square root is about 10⁹ steps, so the primes must be found together.
Constraints
  • 1 <= n <= 10⁶
  • Memory is O(n) bits, which is what caps n in practice
mathsprimessievearray
Open on GeeksforGeeks ↗
02

Intuition

Testing every number for divisors one at a time repeats the same work over and over. The sieve of Eratosthenes algorithm flips the question: instead of asking "is this number prime?", it crosses out every number that is known to be composite.

Write out 2 … n. The smallest number not crossed out is prime, because nothing smaller divides it. Cross out all its multiples, move to the next number still standing, and repeat. Whatever survives is prime.

The demo below runs a sieve of Eratosthenes example on 1 to 30, and the classic sieve of Eratosthenes 1 to 100 grid.

How to spot this pattern

You need many primes, or primality of every number up to a limit: count primes below n (LeetCode 204), prime factorisation of many numbers, or prime-sum puzzles. For a single number, trial division up to √n is enough; the sieve pays off when the same range is queried many times.

03

Approach

Try it first

Before reading on: list the numbers 2 to 30 and cross out multiples by hand. Which prime is the last one you actually need to cross with? Why can you start crossing 5's multiples at 25 instead of 10?

1

Handle n < 2

There are no primes, so return an empty list. This also avoids indexing is_prime[1] in an array of size 1.

2

Mark everything as prime

is_prime = [True] * (n + 1), then set indices 0 and 1 to False. Index i answers "is i prime?". Every number starts innocent; only numbers proven composite get crossed out.

3

Loop p while p × p ≤ n

For each p while p × p ≤ n:

  • is_prime[p] is still True: p is prime, so cross out p×p, p×p + p, p×p + 2p, … up to n;
  • is_prime[p] is False: p is composite and its multiples are already crossed, so skip it.

Any smaller multiple of p has a smaller prime factor and was already crossed out, so starting at p × p skips nothing.

4

Collect the survivors

Every i from 2 to n with is_prime[i] still True is prime. They come out already in increasing order. Anything never crossed out has no divisor between 2 and its square root, so it is prime.

04

Sieve of Eratosthenes solution in Python | C++ | Java

▶1class Solution:
▶2 def sieve(self, n: int) -> List[int]:
▶3 if n < 2:
▶4 return []
▶5 is_prime = [True] * (n + 1)
▶6 is_prime[0] = is_prime[1] = False
▶7 p = 2
▶8 while p * p <= n:
▶9 if is_prime[p]:
▶10 for m in range(p * p, n + 1, p):
▶11 is_prime[m] = False
▶12 p += 1
▶13 return [i for i in range(2, n + 1) if is_prime[i]]
numbers1234567891011121314151617181920212223242526272829302 to 30 start as possible primes
n30upper limit
√n5.48largest crosser needed
Setup. Mark 2 to 30 as possibly prime; 1 is not prime. The sieve will cross out every composite number, and whatever is left standing is prime.
numbers1234567891011121314151617181920212223242526272829304=2×22 is prime → cross from 4
p2prime
start42 × 2
newly crossed144, 6, 8, 10, 12, 14, 16, …, 30
2 is prime: nothing smaller crossed it out. Cross out its multiples starting at 4. 2 × 2 = 4 is the first multiple that is not 2 itself.
numbers1234567891011121314151617181920212223242526272829309=3×33 is prime → cross from 9
p3prime
start93 × 3
newly crossed49, 15, 21, 27
3 is prime: nothing smaller crossed it out. Cross out its multiples starting at 9. Smaller multiples such as 6 were already crossed by a smaller prime, so starting lower would only repeat work.
numbers1234567891011121314151617181920212223242526272829304 already crossed → skip
p4composite
is_prime[4]Falsenothing to do
4 is composite, so every multiple of 4 is also a multiple of a smaller prime (2) and is already crossed out. Skipping it saves a whole pass.
numbers12345678910111213141516171819202122232425262728293025=5×55 is prime → cross from 25
p5prime
start255 × 5
newly crossed125
5 is prime: nothing smaller crossed it out. Cross out its multiples starting at 25. Smaller multiples such as 10 were already crossed by a smaller prime, so starting lower would only repeat work.
numbers12345678910111213141516171819202122232425262728293030>36=6×6p × p > n → stop crossing
p6p × p = 36
loopends36 > 30
Stop at √n. A composite number ≤ 30 is a product a × b, and the smaller factor is at most √30 ≈ 5.5. So it was crossed out by a prime below 6. Everything still standing, including 6 itself if it is uncrossed, is prime.
numbers12345678910111213141516171819202122232425262728293010 survivors → return them
primes10survivors
Collect the survivors. The 10 green numbers were never crossed out, so each has no factor other than 1 and itself. They come out in increasing order because the scan goes from 2 to 30.
05

Common pitfalls

Crossing out p itself

✗ Wrong
for m in range(p, n + 1, p):
✓ Right
for m in range(p * p, n + 1, p):

Starting at p marks the prime as composite, so the result loses every prime. Starting at 2 * p is correct but repeats work; p * p is the first multiple not already crossed.

Stopping the outer loop at p < √n

✗ Wrong
while p * p < n:
✓ Right
while p * p <= n:

For n = 25 the loop stops before p = 5, so 25 is never crossed out and is returned as a prime.

06

Complexity

Time
O(n log log n)
Space
O(n)
Almost linear in practice; the FAQ below shows where log log n comes from. The boolean array of n + 1 flags is the memory cost, and it is what limits how large n can be.
07

Sieve of Eratosthenes FAQ

How does the sieve of Eratosthenes work?
  • Setup: mark every number from 2 to n as prime.
  • Loop: for p = 2, 3, … while p × p ≤ n, if p is still marked, cross out p², p² + p, p² + 2p, ….
  • Result: the numbers still marked are exactly the primes.
  • Why it works: every composite ≤ n has a prime factor ≤ √n, so it is crossed out by that factor.
  • Complexity: O(n log log n) time, O(n) space.
What does the sieve of Eratosthenes 1 to 100 look like?

Cross out multiples of 2 (from 4), 3 (from 9), 5 (from 25) and 7 (from 49). The next prime, 11, has 11² = 121 > 100, so the sieve stops. The 25 survivors are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97.

What is the sieve of Eratosthenes time complexity?

O(n log log n). Each prime p crosses out about n / p numbers, and the sum of 1 / p over primes up to n grows like log log n. The space is O(n) for the array of flags.

Is the sieve of Eratosthenes on LeetCode?

Yes, as the intended solution to LeetCode 204, Count Primes, which asks how many primes are strictly less than n. Run the same sieve up to n - 1 and count the survivors.

← Prev · GFG
Shortest Job First
Next · GFG →
Sort a Stack