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.
Facts
Time ComplexityO(n log log n) operations on a random access machine. 2 Credited ToEratosthenes of Cyrene, 3rd century BC. 2 Time Complexity
Time Complexity (category)Linearithmic Time -- O(n log n) 1 Connections
In Field
Source Wikipedia: Sieve of Eratosthenes
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. Sieve of Eratosthenes (Wikipedia)
Wikipedia infobox: time complexity linearithmicQuote, Wikipedia infobox: time complexity linearithmic
linearithmic
2. 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.
In Field: Algorithms and Complexity Theory, Lead sentence
sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.
View the Source Wikidata: Sieve of Eratosthenes
Wikidata Q177898, class allow-list match (w-wdresolver-0926)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.