Eratosthenes: Difference between revisions
Jump to navigation
Jump to search
imported>Pat Palmer mNo edit summary |
imported>Pat Palmer (linking to algorithm) |
||
| Line 2: | Line 2: | ||
'''Eratosthenes''' (ca. 276 B.C.–ca. 195 B.C.) was a [[Greek]] [[mathematician]] and [[astronomer]]. He is best known today for his calculation of the [[circumference of the Earth]]. | '''Eratosthenes''' (ca. 276 B.C.–ca. 195 B.C.) was a [[Greek]] [[mathematician]] and [[astronomer]]. He is best known today for his calculation of the [[circumference of the Earth]]. | ||
The ''sieve of Eratosthenes'' is a mathematical algorithm for finding all prime numbers up to a certain value, say ''N''. After first writing down all the numbers up to ''N'', every multiple of 2 can then be crossed out, then every multiple of 3, 5, 7, 11, and so on for every prime number less than or equal to the ''square root'' of ''N''. In this way, composite numbers are filtered or sifted out of the written list of numbers, leaving only prime numbers remaining. | The ''sieve of Eratosthenes'' is a mathematical [[Algorithm|algorithm]] for finding all prime numbers up to a certain value, say ''N''. After first writing down all the numbers up to ''N'', every multiple of 2 can then be crossed out, then every multiple of 3, 5, 7, 11, and so on for every prime number less than or equal to the ''square root'' of ''N''. In this way, composite numbers are filtered or sifted out of the written list of numbers, leaving only prime numbers remaining. | ||
Revision as of 23:24, 6 December 2020
Eratosthenes (ca. 276 B.C.–ca. 195 B.C.) was a Greek mathematician and astronomer. He is best known today for his calculation of the circumference of the Earth.
The sieve of Eratosthenes is a mathematical algorithm for finding all prime numbers up to a certain value, say N. After first writing down all the numbers up to N, every multiple of 2 can then be crossed out, then every multiple of 3, 5, 7, 11, and so on for every prime number less than or equal to the square root of N. In this way, composite numbers are filtered or sifted out of the written list of numbers, leaving only prime numbers remaining.