Eratostnes´sil

Eratostenes sil er en metode for å finne primtall mindre enn et gitt tall. Vi skriver opp alle tallene fra 2 til den øvre grensen. Om vi skriver ned tallene fra 2 til og med 100, kan vi sile ut tallene som ikke er primtall. Dette gjør vi ved å

  1. Stryk alle tall som er delelig med 2, men ikke tallet 2
  2. Stryk de tallene som er igjen som er delelig med 3 utenom 3
  3. Stryk alle tall som er delelig med 5 utenom tallet 5 selv
  4. Stryk alle tall som er delelig med 7 utenom tallet 7 selv

Om det øverste tallet er 100 står du nå igjen med tallene

2 3 5 7 11 13 17 19
23 29 31 37
41 43 47 53 59
61 67 71 73 79
83 89 97

Vi vet at sammensatte tal mindre eller lik 100 har minst en primfaktor mindre eller lik \sqrt{100}=10. Derfor inneholder listen nå primtall som er mindre eller lik 100