Sieve of Eratosthenes

From Academic Kids

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

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:埃拉托斯特尼筛法

Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools