The sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a given limit, by iteratively marking as composite the multiples of each prime starting from 2, so that the numbers left unmarked at the end are exactly the primes. It is attributed to Eratosthenes of Cyrene, a third-century BC Greek mathematician, though the earliest surviving reference to it appears in Nicomachus of Gerasa's early second-century AD Introduction to Arithmetic. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Time ComplexityO(n log log n) operations on a random access machine. 1 Credited ToEratosthenes of Cyrene, 3rd century BC. 1 Connections
Predecessor Of
Verified en.wikipedia.org/wiki/Sieve_of_Atkin: "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."
Sources
1. Wikipedia: Sieve of Eratosthenes
Wikimedia FoundationLead section
In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.
Body, complexity discussion
The time complexity of calculating all primes below n in the random access machine model is O(n log log n) operations.
Body, history
Eratosthenes of Cyrene, a 3rd-century BCE Greek mathematician.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.