Editing Prime number (section)

=== Sieves ===
[[File:Sieve of Eratosthenes animation.gif|frame|The [[sieve of Eratosthenes]] starts with all numbers unmarked (gray). It repeatedly finds the first unmarked number, marks it as prime (dark colors) and marks its square and all later multiples as composite (lighter colors). After marking the multiples of 2 (red), 3 (green), 5 (blue), and 7 (yellow), all primes up to the square root of the table size have been processed, and all remaining unmarked numbers (11, 13, etc.) are marked as primes (magenta).|alt=Animation of the sieve of Eratosthenes]]

{{main|Sieve of Eratosthenes}}
Before computers, [[mathematical table]]s listing all of the primes or prime factorizations up to a given limit were commonly printed.<ref>{{cite journal| first=Maarten |last=Bullynck |title=A history of factor tables with notes on the birth of number theory 1657–1817 |journal=Revue d'Histoire des Mathématiques |year=2010 |pages=133–216 |volume=16 |issue=2 |url=https://hal-univ-paris8.archives-ouvertes.fr/hal-01103903/ }}</ref> The oldest known method for generating a list of primes is called the sieve of Eratosthenes.<ref>{{cite book |title=The Joy of Factoring |volume=68 |series=Student mathematical library |first=Samuel S. Jr. |last=Wagstaff |author-link=Samuel S. Wagstaff Jr. |publisher=American Mathematical Society |year=2013 |isbn=978-1-4704-1048-3 |page=191 |url=https://books.google.com/books?id=rowCAQAAQBAJ&pg=PA191 }}</ref> The animation shows an optimized variant of this method.<ref>{{cite book |title=Prime Numbers: A Computational Perspective |edition=2nd |first1=Richard |last1=Crandall |author1-link=Richard Crandall |first2=Carl |last2=Pomerance |author2-link=Carl Pomerance |publisher=Springer |year=2005 |isbn=978-0-387-25282-7 |page=121 |url=https://books.google.com/books?id=RbEz-_D7sAUC&pg=PA121 }}</ref> Another more asymptotically efficient sieving method for the same problem is the [[sieve of Atkin]].<ref>{{cite conference | last1 = Farach-Colton | first1 = Martín | author1-link = Martin Farach-Colton | last2 = Tsai | first2 = Meng-Tsung | editor1-last = Elbassioni | editor1-first = Khaled | editor2-last = Makino | editor2-first = Kazuhisa | arxiv = 1504.05240 | contribution = On the complexity of computing prime tables | doi = 10.1007/978-3-662-48971-0_57 | pages = 677–688 | publisher = Springer | series = Lecture Notes in Computer Science | title = Algorithms and Computation: 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings | volume = 9472 | year = 2015| isbn = 978-3-662-48970-3 }}</ref> In advanced mathematics, [[sieve theory]] applies similar methods to other problems.<ref>{{cite book|title=Sieves in Number Theory|volume=43|series=Ergebnisse der Mathematik und ihrer Grenzgebiete (3. Folge)|first=George|last=Greaves|publisher=Springer|year=2013|isbn=978-3-662-04658-6|page=1|url=https://books.google.com/books?id=G0TtCAAAQBAJ&pg=PA1}}</ref>