✦ScienexySCIENCE KNOWLEDGE LIBRARY
algorithm · SCI-MAT-002-052

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

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.

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

NameDescription

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

ProblemSolution

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