Eratosthenes’ sil

Eratosthenes' sil er en enkel og gammel algoritme for å finne alle primtall opp til et spesifikt naturlig tall. Metoden var forgjengeren til den noe nyere Atkins sil, som er raskere, men mye mer kompleks.

Eratosthenes' sil brukt for å finne primtall under 120.

Metoden ble utviklet av Eratosthenes, en gresk matematiker som levde ca. 200 f.Kr.

Kretsfaktorisering blir ofte brukt på listen over tallene der primtallene skal lukes ut før Eratosthenes' sil blir brukt, for at det skal gå raskere.

Algoritmen

Et primtall er et naturlig tall høyere enn 1 og som bare kan deles på 1 og seg selv uten å gi rest.

For å finne alle primtall mindre enn eller lik et gitt heltall n ved hjelp av Eratosthenes' metode:

1. Lag en liste av påfølgende heltall fra 2 til n: (2, 3, 4, ..., n).
2. La p til å begynne med være lik 2, det første primtallet.
3. Stryk ut alle multipler av p som er større enn eller lik p*p, fra listen.
4. Finn det første tallet større enn p som står igjen på listen. Dette tallet er det neste primtallet. Sett p lik dette tallet.
5. Gjenta trinn 3 og 4 inntil p² er større enn n.
6. Alle gjenværende tall på listen er primtall.

Eksempel

For å finne alle primtall mindre enn eller lik 30 går man frem som følger:

Lag først en liste over heltall fra 2 til 30:

  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Stryk ut (sil ut) multipler av 2, dette gir:

  2  3     5     7     9    11    13    15    17    19    21    23    25    27    29

Det første tallet på listen etter 2 er 3; stryk ut multipler av 3 fra listen, dette gir:

  2  3     5     7          11    13          17    19          23    25          29

Det første tallet på listen etter 3 er 5; stryk ut de gjenværende multiplene av 5 fra listen:

  2  3     5     7          11    13          17    19          23                29

Det første tallet på listen etter 5 er 7, men kvadratet av 7 er 49, som er større enn 30, 
så prosessen er ferdig. Den endelige listen består av alle primtall mindre enn eller lik 30.

Eksterne lenker

• Analyse av Erastosthenes' sil
• Interaktiv JavaScript tilleggsprogram Arkivert 1. mars 2001 hos Wayback Machine.