Eratosthenes' sil

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk
Eratosthenes' sil brukt for å finne primtall under 120.

Eratosthenes' sil er i matematikk en enkel, eldgammel 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.

Metoden ble utviklet av Eratosthenes, en gresk matematiker som levde et par hundre år før Kristus. 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.

Algoritme[rediger | rediger kilde]

Et primtall er et naturlig tall 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 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 p2 er større enn n.
  6. Alle gjenværende tall på listen er primtall.

Eksempel[rediger | rediger kilde]

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[rediger | rediger kilde]