Eratosthenes: Difference between revisions
imported>Mark Widmer (Sieve of Eratosthenes: Corrected algorith -- e.g. 2 itself is not crossed out. Added explanation of why algorithm can be stopped at sqrt(N).) |
imported>Mark Widmer (Added section "Scientific and mathematical work") |
||
| Line 1: | Line 1: | ||
{{subpages}} | {{subpages}} | ||
'''Eratosthenes''' (ca. 276 B.C.–ca. 195 B.C.) was a [[Greek]] [[Mathematics|mathematician]] and [[Astronomy|astronomer]]. He is best known today for his calculation of the [[circumference of | '''Eratosthenes''' (ca. 276 B.C.–ca. 195 B.C.) was a [[Greek]] [[Mathematics|mathematician]] and [[Astronomy|astronomer]]. He is best known today for his calculation of the [[Circle_(mathematics)|circumference]] of [[Earth]]. | ||
==Scientific and mathematical work== | |||
Eratosthenes made the first known calculation of the circumference of Earth. | |||
In mathematics, the ''sieve of Eratosthenes'' is an [[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, ''except for 2 itself''. Then multiples of 3, 5, 7, 11, and so on for every prime number less than or equal to the ''square root'' of ''N'', are crossed out. In this way, composite numbers are filtered or sifted out of the written list of numbers, leaving only prime numbers remaining. (For prime numbers larger than the square root of ''N'', note that e.g. twice the number would already be crossed off the list, and similarly for all other multiples that are less than or equal to ''N''.) | In mathematics, the ''sieve of Eratosthenes'' is an [[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, ''except for 2 itself''. Then multiples of 3, 5, 7, 11, and so on for every prime number less than or equal to the ''square root'' of ''N'', are crossed out. In this way, composite numbers are filtered or sifted out of the written list of numbers, leaving only prime numbers remaining. (For prime numbers larger than the square root of ''N'', note that e.g. twice the number would already be crossed off the list, and similarly for all other multiples that are less than or equal to ''N''.) | ||
Latest revision as of 19:13, 7 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 Earth.
Scientific and mathematical work
Eratosthenes made the first known calculation of the circumference of Earth.
In mathematics, the sieve of Eratosthenes is an 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, except for 2 itself. Then multiples of 3, 5, 7, 11, and so on for every prime number less than or equal to the square root of N, are crossed out. In this way, composite numbers are filtered or sifted out of the written list of numbers, leaving only prime numbers remaining. (For prime numbers larger than the square root of N, note that e.g. twice the number would already be crossed off the list, and similarly for all other multiples that are less than or equal to N.)