Difference between revisions of "Eratosthenes, sieve of"
m (→References: isbn link) |
(details) |
||
| Line 1: | Line 1: | ||
A method worked out by Eratosthenes (3rd century B.C.) for eliminating composite numbers from the sequence of natural numbers. The essence of the sieve of Eratosthenes consists in the following. First the number 1 is crossed out. Now 2 is a prime number. Next all numbers divisible by 2 are crossed out. Now 3, the first number not crossed out, is a prime number. Then all the numbers divisible by 3 are crossed out. Now 5, the first number not crossed out, is a prime number. Continuing in this way one can find an arbitrary large segment of the sequence of prime numbers. | A method worked out by Eratosthenes (3rd century B.C.) for eliminating composite numbers from the sequence of natural numbers. The essence of the sieve of Eratosthenes consists in the following. First the number 1 is crossed out. Now 2 is a prime number. Next all numbers divisible by 2 are crossed out. Now 3, the first number not crossed out, is a prime number. Then all the numbers divisible by 3 are crossed out. Now 5, the first number not crossed out, is a prime number. Continuing in this way one can find an arbitrary large segment of the sequence of prime numbers. | ||
| − | In 1808 A.M. Legendre used the ideas of this sieve to derive an estimate for the [[distribution of prime numbers]] of the form $\pi(x) < x/\log\log x$. | + | In 1808, [[Legendre, Adrien-Marie|A.-M. Legendre]] used the ideas of this sieve to derive an estimate for the [[distribution of prime numbers]] of the form $\pi(x) < x/\log\log x$. |
The sieve of Eratosthenes has been developed into other stronger [[sieve method]]s, such as, for example, the [[Brun theorem|Brun sieve]]. | The sieve of Eratosthenes has been developed into other stronger [[sieve method]]s, such as, for example, the [[Brun theorem|Brun sieve]]. | ||
| Line 10: | Line 10: | ||
====References==== | ====References==== | ||
<table> | <table> | ||
| − | <TR><TD valign="top">[a1]</TD> <TD valign="top"> | + | <TR><TD valign="top">[a1]</TD> <TD valign="top"> Glyn Harman, "Eratosthenes, Legendre, Vinogradov and beyond", ''Sieve Methods, Exponential Sums, and Their Applications in Number Theory'', |
| − | + | ed. G. R. H. Greaves, G. Harman, M. N. Huxley; London Mathematical Society Lecture Note Series '''237''', Cambridge University Press (1997) {{ISBN|0-521-58957-6}} {{ZBL|1013.11062}}</TD></TR> | |
</table> | </table> | ||
Latest revision as of 10:32, 30 March 2024
A method worked out by Eratosthenes (3rd century B.C.) for eliminating composite numbers from the sequence of natural numbers. The essence of the sieve of Eratosthenes consists in the following. First the number 1 is crossed out. Now 2 is a prime number. Next all numbers divisible by 2 are crossed out. Now 3, the first number not crossed out, is a prime number. Then all the numbers divisible by 3 are crossed out. Now 5, the first number not crossed out, is a prime number. Continuing in this way one can find an arbitrary large segment of the sequence of prime numbers.
In 1808, A.-M. Legendre used the ideas of this sieve to derive an estimate for the distribution of prime numbers of the form $\pi(x) < x/\log\log x$.
The sieve of Eratosthenes has been developed into other stronger sieve methods, such as, for example, the Brun sieve.
Comments
For references see also Sieve method.
References
| [a1] | Glyn Harman, "Eratosthenes, Legendre, Vinogradov and beyond", Sieve Methods, Exponential Sums, and Their Applications in Number Theory, ed. G. R. H. Greaves, G. Harman, M. N. Huxley; London Mathematical Society Lecture Note Series 237, Cambridge University Press (1997) ISBN 0-521-58957-6 Zbl 1013.11062 |
Eratosthenes, sieve of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Eratosthenes,_sieve_of&oldid=55695