Module 25 · Bit Manipulation, Mathematics, and Designed Data Structures

247. Sieve of Eratosthenes

Bridge · Download this solution · All solutions and shared helpers

Problem

Return all prime integers less than or equal to n in ascending order, for n>=0. A prime is an integer greater than one with no positive divisors other than one and itself. Return [] when n<2. Use the Sieve of Eratosthenes.

Examples

Example 1

sieve_primes(20)
=> [2, 3, 5, 7, 11, 13, 17, 19]

All and only primes up to the inclusive endpoint survive.

Example 2

sieve_primes(1)
=> []

Neither zero nor one is prime.

Example 3

sieve_primes(2)
=> [2]

The first prime survives without any marking pass.

Reveal the worked solution and reasoning

Why this mechanism works

Initially treat values at least two as candidates. For each still-unmarked p through sqrt(n), mark its multiples. Begin at p*p because smaller multiples p*k with k<p already have a smaller prime factor and were handled earlier. Every composite has a prime factor no larger than its square root.

State and boundaries

prime[x] remains true only if no processed prime factor divides x. When p is reached unmarked, no smaller prime divides it, so p is prime.

Protocol

Handle n<2.
Allocate true flags and clear zero and one.
For candidate p while p*p<=n, if unmarked then clear multiples from p*p.
Return every remaining true index.

Visualization

p=2 marks 4,6,8,10,...
p=3 starts at 9; 6 was already handled by 2
unmarked values begin 2,3,5,7,11,...

Python implementation

def sieve_primes(n):
    if n < 2:
        return []
    prime = [True] * (n + 1)
    prime[0] = prime[1] = False
    p = 2
    while p * p <= n:
        if prime[p]:
            for multiple in range(p * p, n + 1, p):
                prime[multiple] = False
        p += 1
    return [value for value in range(2, n + 1) if prime[value]]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

sieve_primes(20)

L2 sieve_primes: if n < 2:
n=20

L4 sieve_primes: prime = [True] * (n + 1)
n=20; prime=[True, True, True, True, True, True, True, True, ...]

L5 sieve_primes: prime[0] = prime[1] = False
n=20; prime=[False, False, True, True, True, True, True, True, ...]

L6 sieve_primes: p = 2
n=20; prime=[False, False, True, True, True, True, True, True, ...]; p=2

L9 sieve_primes: for multiple in range(p * p, n + 1, p):
n=20; prime=[False, False, True, True, True, True, True, True, ...]; p=2; multiple=4

L10 sieve_primes: prime[multiple] = False
n=20; prime=[False, False, True, True, False, True, True, True, ...]; p=2; multiple=4

L9 sieve_primes: for multiple in range(p * p, n + 1, p):
n=20; prime=[False, False, True, True, False, True, True, True, ...]; p=2; multiple=6

L10 sieve_primes: prime[multiple] = False
n=20; prime=[False, False, True, True, False, True, False, True, ...]; p=2; multiple=6

... 30 intermediate state changes omitted ...

L12 sieve_primes: return [value for value in range(2, n + 1) if prime[value]]
n=20; prime=[False, False, True, True, False, True, False, True, ...]; p=5; multiple=18; value=18

L12 sieve_primes: return [value for value in range(2, n + 1) if prime[value]]
n=20; prime=[False, False, True, True, False, True, False, True, ...]; p=5; multiple=18; value=19

L12 sieve_primes: return [value for value in range(2, n + 1) if prime[value]]
n=20; prime=[False, False, True, True, False, True, False, True, ...]; p=5; multiple=18; value=20

L12 sieve_primes: return [value for value in range(2, n + 1) if prime[value]]
n=20; prime=[False, False, True, True, False, True, False, True, ...]; p=5; multiple=18

Result: [2, 3, 5, 7, 11, 13, 17, 19]. All and only primes up to the inclusive endpoint survive.

sieve_primes(1)

L2 sieve_primes: if n < 2:
n=1

Result: []. Neither zero nor one is prime.

Why the solution is correct

Only proper multiples of confirmed primes are removed, so primes are never removed. Every composite x has a prime factor p<=sqrt(x)<=sqrt(n); it is marked during that p pass. Therefore the remaining flags correspond exactly to primes, and the final ascending scan orders them.

Time and space

O(n log log n) marking time plus O(n) initialization/output scan, and O(n) auxiliary flags.

Common mistakes

Leaving one marked true incorrectly calls it prime. Starting at p rather than p*p erases the prime itself.

Reasoning card

State: prime[x] remains true only if no processed prime factor divides x. When p is reached unmarked, no smaller prime divides it, so p is prime.

Invariant: Unmarked values below the current frontier have correct primality status.

Decision to rehearse: Mark multiples starting from p*p.

Finish: Return every remaining true index

Transfer exercise

Implement a segmented sieve for a large interval using base primes only through the square root of its upper bound.