FoundationSource checked

Sieve of Eratosthenes

Finds all primes up to a limit by repeatedly crossing out multiples of each discovered prime.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Numerical Methods
Difficulty: Beginner
Family: Number Theory
Tier: Foundation
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 0
Relationships: 4
Code example: Ready
Visualization: Ready

Overview

The Sieve of Eratosthenes keeps a table of candidate integers and marks multiples of each prime starting at p squared. Unmarked values that remain are prime.

Core Concepts

primecomposite markingmultiplessquare root bound

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n log log n)

Average

O(n log log n)

Worst

O(n log log n)

Space

O(n)

When to Use

Use it when all primes up to a moderate limit are needed.
Use it when a table of primality values is useful for later queries.
Use segmented variants when the limit is large but memory is limited.

When Not to Use

Avoid it when only one very large number needs a primality test.
Avoid storing the full table when the range is too large for memory.
Avoid starting multiples below p squared because earlier primes already handled them.

What It Does

Enumerates primes up to a limit
Eliminates composite numbers by marking multiples

Use Cases

Prime tables
Number-theory preprocessing
Teaching prime generation

Inputs

Numbers, vectors, matrices, or functions
Tolerance or precision settings

Outputs

Computed numeric result
Residual, factorization, or approximation

Pseudocode

1.Create a boolean table for 0 through n.
2.Mark 0 and 1 as nonprime.
3.For p from 2 while p * p <= n:
4.If p is still marked prime, mark multiples from p * p through n.
5.Return every index still marked prime.

Canonical Example

Input: n = 20
Output: [2, 3, 5, 7, 11, 13, 17, 19]
Explanation: Multiples of 2, 3, and then 5 and above as needed are marked composite; unmarked values are prime.

Implementation Notes

Initialize candidates from 2 through n.
For each unmarked p up to sqrt(n), mark p*p, p*p+p, and so on.
Consider storing only odd numbers after handling 2.

Common Pitfalls

Marking multiples from 2p instead of p squared and doing extra work.
Treating 0 or 1 as prime.
Using too much memory for a very large upper bound.

Interactive Mechanism Walkthrough

Iterative Convergence & State Trajectory

Show crossing out multiples of each discovered prime on a small prime generation example.

Step 1 of 5: Create a boolean table for 0 through n.

numerical-methods-mechanism

Notes

For a single large candidate, probabilistic or deterministic primality tests are usually more appropriate than sieving up to that number.

Sources (2)

What each reference supports for this entry.

Modern Computer Arithmetic

Book

Reference for Sieve of Eratosthenes's arithmetic operations, modular arithmetic, multiplication, division, or number-theoretic implementation details.

Open source