Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Sieve of Eratosthenes
Summary
In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.
It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime. This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime. Once all the multiples of each discovered prime have been marked as composites, the remaining unmarked numbers are primes.
The earliest known reference to the sieve (κόσκινον Ἐρατοσθένους, kóskinon Eratosthénous) is in Nicomachus of Gerasa's Introduction to Arithmetic, an early 2nd cent. CE book which attributes it to Eratosthenes of Cyrene, a 3rd cent. BCE Greek mathematician, though describing the sieving by odd numbers instead of by primes.
One of a number of prime number sieves, it is one of the most efficient ways to find all of the smaller primes. It may be used to find primes in arithmetic progressions.
Sift the Two's and Sift the Three's:The Sieve of Eratosthenes.When the multiples sublime,The numbers that remain are Prime.
A prime number is a natural number that has exactly two distinct natural number divisors: the number 1 and itself.
To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:
Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
Initially, let p equal 2, the smallest prime number.
Enumerate the multiples of p by counting in increments of p from 2p to n, and mark them in the list (these will be 2p, 3p, 4p, ...; the p itself should not be marked).
Find the smallest number in the list greater than p that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Ontological neighbourhood
Related courses (4)
MATH-521: Advanced analytic number theory
We will present the work of James Maynard (MF 2022) on the existence of bounded gaps between primes
MATH-489: Number theory II.c - Cryptography
The goal of the course is to introduce basic notions from public key cryptography (PKC) as well as basic number-theoretic methods and algorithms for cryptanalysis of protocols and schemes based on PKC
CS-101: Advanced information, computation, communication I
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
Related lectures (19)
Integer Factorization: Quadratic Sieve
Covers the Quadratic Sieve method for integer factorization, emphasizing the importance of choosing the right parameters for efficient factorization.
Ceramic Materials Processing: Techniques and Analysis
Explores ceramic materials processing techniques like laser diffraction, sieving, sedimentation testing, slip casting, and density determination.
Computing with Infinite Sequences
Introduces lazy lists for computing infinite sequences like prime numbers.
Related publications (8)
Crystal, defect, and morphology engineering of porous two-dimensional materials for ionic separation
Ordered two-dimensional (2D) materials hosting Å-scale pores are highly promising for enabling challenging separation, thanks to well-defined pore geometry resulting in tight confinement of ions when hosted inside the pore. In addition, the 2D nature of th ...
EPFL2024Mass transport of water vapor and ions from Å-scale graphene nanopores
Hydrodynamics at the nanoscale involves both fundamental study and application of fluid and mass transport phenomena in nanometer-sized confinements. Nanopores in single-layer graphene can be highly attractive for exploring the molecular transport of gas a ...
EPFL2022Testing different (e)DNA metabarcoding approaches to assess aquatic oligochaete diversity and the biological quality of sediments
Aquatic oligochaetes are important bioindicators of sediment quality in watercourses and lakes, but their morphological identification to the species level is challenging and sometimes impossible. The use of DNA barcoding and metabarcoding could greatly fac ...
2019Related concepts (9)
Sieve theory
Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. The prototypical example of a sifted set is the set of prime numbers up to some prescribed limit X. Correspondingly, the prototypical example of a sieve is the sieve of Eratosthenes, or the more general Legendre sieve. The direct attack on prime numbers using these methods soon reaches apparently insuperable obstacles, in the way of the accumulation of error terms.
Primality test
A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (its running time is polynomial in the size of the input).
Sieve of Atkin
In mathematics, the sieve of Atkin is a modern algorithm for finding all prime numbers up to a specified integer. Compared with the ancient sieve of Eratosthenes, which marks off multiples of primes, the sieve of Atkin does some preliminary work and then marks off multiples of squares of primes, thus achieving a better theoretical asymptotic complexity. It was created in 2003 by A. O. L. Atkin and Daniel J. Bernstein. In the algorithm: All remainders are modulo-sixty remainders (divide the number by 60 and return the remainder).