Difference between revisions of "Eratosthenes, sieve of"
From Encyclopedia of Mathematics
(Importing text file) |
(Category:Number theory) |
||
| 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. The sieve of Eratosthenes has been developed into other stronger sieve | + | 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. The sieve of Eratosthenes has been developed into other stronger [[sieve method]]s, such as, for example, the [[Brun theorem|Brun sieve]]. |
| + | ====Comments==== | ||
| + | For references see [[Sieve method]]. | ||
| − | + | [[Category:Number theory]] | |
| − | |||
| − | |||
Revision as of 17:58, 1 November 2014
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. The sieve of Eratosthenes has been developed into other stronger sieve methods, such as, for example, the Brun sieve.
Comments
For references see Sieve method.
How to Cite This Entry:
Eratosthenes, sieve of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Eratosthenes,_sieve_of&oldid=17311
Eratosthenes, sieve of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Eratosthenes,_sieve_of&oldid=17311
This article was adapted from an original article by B.M. Bredikhin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article