Sieve of Eratosthenes
Criba de Eratóstenes
- Date
- c. 240 BCE · confidence medium
- Place
- Alexandria, Egypt
- Credited to
- Eratosthenes of Cyrene
- People
- 👤 Eratóstenes276 BCE–194 BCE
- Field
- Knowledge & symbols
What was discovered
Algorithm for listing all primes up to a limit by successively crossing out the multiples of each prime. It is the first systematic method for generating primes.
Known through Nicomachus of Gerasa (1st century CE).
What it led to
- sieve methods (Brun, Selberg)
- analytic number theory
- the computation of prime tables
Built on
- Infinitude of primesc. 300 BCE
- infinitude of primes
Made possible
- Brun's theorem1919
- Quadratic sieve1981
- primality tests