Sieve of Eratosthenes
|
|
In mathematics, the sieve of Eratosthenes is a simple algorithm for finding all the prime numbers up to a specified integer. You start with a list of all integers beginning with 2 and at every step, you remove the smallest number (which is a prime) and all multiples of this number (which are composite).
In more detail, the algorithm goes as follows
Step 1. List the integers, starting with "2".
- 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Step 2. Mark the first number in the list as prime.
- Known primes: 2
- Main list: 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Step 3. Step through the main list eliminating all multiples of the number just added to the list of known primes.
- Known primes: 2
- Main list: 3 5 7 9 11 13 15 17 19
Step 4. If the largest number in the main list is less than the square of the largest number in the known prime list, mark all numbers in the main list as prime; otherwise, return to Step 2.
- Since 19 is greater than the square of 2 (4), we return to Step 2:
- Known primes: 2 3
- Main list: 5 7 9 11 13 15 17 19
- Then step 3:
- Known primes: 2 3
- Main list: 5 7 11 13 17 19
- 19 is greater than the square of 3 (9), so we return to step 2:
- Known primes: 2 3 5
- Main list: 7 11 13 17 19
- Then step 3 (no changes to either list).
- 19 is less than the square of 5 (25), so the remaining list is prime.
- RESULT: The primes in the range 2 to 20 are: 2, 3, 5, 7, 11, 13, 17, 19.
Reference
Κοσκινον Ερατοσθενους or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, by the Rev. Samuel Horsley, F. R. S., Philosophical Transactions (1683-1775), Vol. 62. (1772), pp. 327-347.
For more advanced developments, see:
External links
- Interactive animation (JavaScript required) (http://www.faust.fr.bw.schule.de/mhb/eratosiv.htm)
- Sieve of Eratosthenes (http://www.cut-the-knot.org/Curriculum/Arithmetic/Eratosthenes.shtml) (requires Java)cs:Eratosthenovo sto
de:Sieb des Eratosthenes es:Criba de Eratstenes fr:Crible d'ratosthne he:המסננת של ארתוסתנס it:Crivello di Eratostene lt:Eratosteno rėtis nl:Zeef van Eratosthenes ja:エラトステネスの篩 pl:Sito Eratostenesa ru:Решето Эратосфена sl:Eratostenovo sito fi:Eratostheneen seula sv:Eratosthenes sll zh:埃拉托斯特尼筛法