The Sieve of Eratosthenes begins by listing all integers from 2 up to a chosen limit n. Initially, every number is considered a possible prime. Starting with 2, the algorithm marks all multiples of each prime as composite. It then moves to the next unmarked number and repeats the process. The procedure only needs to consider prime numbers up to the square root of n because every composite number not exceeding n must have at least one prime factor no greater than √n. When the process finishes, all unmarked numbers are prime.
Sieve of Eratosthenes
The Sieve of Eratosthenes is an ancient and efficient algorithm for finding all prime numbers up to a specified limit by repeatedly eliminating multiples of known primes.
For each prime p, mark multiples p², p² + p, p² + 2p, ..., while the multiple is ≤ n.
Explanation
Variables
P
The current prime number.
N
The maximum integer in the search range.
P²
The first multiple of p that needs to be marked during the optimized sieve.
√n
The upper bound for the prime numbers used in the marking process.
Example or application
A worked example has not yet been added.
Definition
The Sieve of Eratosthenes is an algorithm that identifies all prime numbers up to a given integer by systematically removing multiples of prime numbers.
Purpose
To find all prime numbers within a specified range efficiently.
Importance
It is one of the simplest and most effective methods for generating prime numbers up to a fixed limit and is widely used in programming and computational number theory.
Key Concepts
Prime identification
Composite number elimination
Multiples
Crossing out
Square-root limit
Boolean arrays
Algorithmic complexity
Characteristics
It identifies all primes up to a fixed limit.
It starts with the smallest prime, 2.
Multiples of each discovered prime are marked as composite.
The marking process only needs to continue while p² ≤ n.
The algorithm can be implemented using a Boolean array.
It is especially efficient for generating many primes within a moderate range.
Types
| Name | Description |
|---|---|
Basic Sieve | Uses a list or array to mark multiples of each prime. |
Optimized Sieve | Begins marking multiples from p² and avoids unnecessary operations. |
Segmented Sieve | Processes a large interval in smaller blocks to reduce memory usage. |
Components
Upper limit n
Candidate number array
Prime indicator
Multiple-marking process
Square-root stopping condition
Properties
All numbers below 2 are excluded from the prime list.
A number that remains unmarked after the process is prime.
Marking begins at p² because smaller multiples have already been eliminated by smaller prime factors.
The algorithm has time complexity approximately O(n log log n).
The standard implementation requires O(n) memory.
Examples
| Problem | Solution |
|---|---|
Find all prime numbers up to 20. | Start with the numbers 2 through 20. Mark multiples of 2, then multiples of 3, and then multiples of 5. The remaining unmarked numbers are 2, 3, 5, 7, 11, 13, 17, and 19. |
Why can the sieve stop checking primes after √20? | √20 is approximately 4.47. Every composite number up to 20 has a prime factor no greater than √20, so checking primes 2 and 3 is sufficient. |
Why does marking begin at p²? | Every smaller multiple of p has already been marked while processing a smaller prime factor. |
Applications
Generating prime-number lists
Competitive programming
Number theory research
Prime-based mathematical experiments
Educational programming exercises
Prerequisites
Prime and composite numbers
Multiplication
Factors and multiples
Square roots
Basic algorithms
Learning Objectives
Explain how the Sieve of Eratosthenes works.
Apply the algorithm to a small range of integers.
Understand why marking begins at p².
Explain why checking primes up to √n is sufficient.
Recognize its time and space complexity.
Understand the purpose of segmented sieving.
Common Mistakes
Including 1 in the prime list.
Marking the prime number itself as composite.
Starting to mark multiples at 2p instead of the optimized starting point p².
Continuing unnecessarily beyond √n.
Forgetting to mark all multiples within the selected range.
Practice Questions
Use the Sieve of Eratosthenes to find all primes up to 30.
Why is 1 excluded from the sieve?
Why does the optimized algorithm start marking at p²?
What is the approximate time complexity of the standard sieve?
What is the purpose of a segmented sieve?
How many prime numbers are there up to 50?
Key Takeaway
The Sieve of Eratosthenes efficiently generates prime numbers by eliminating multiples of smaller primes.
Related Topics
Prime Numbers
Composite Numbers
Prime Factorization
Algorithmic Complexity
Segmented Sieve
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Source verification pending; check an authoritative textbook, university, standards body, or peer-reviewed source.
Suggest a correction or source · More in Arithmetic & Number Theory