Eratosthenes såll

Från Wikipedia
Hoppa till: navigering, sök
Eratosthenes såll på talen 2-10. Här uppdelat i steg för att visa vad som händer.

Eratosthenes såll är en enkel algoritm som uppfanns av greken Eratosthenes och används för att hitta primtal.

Algoritmen[redigera | redigera wikitext]

Eratosthenes såll på talen 2-120.

(Bilden visar att vissa tal stryks mer än en gång. En förfinad variant är att talen tas bort istället och effektiviserar på så sätt sökandet. Det framgår inte om detta var avsikten från början.) Sållet används så här:

  1. Gör en lista över alla tal från två till något valbart största tal n.
  2. Stryk ut från listan alla jämna tal som är större än två (4, 6, 8 osv.).
  3. Listans nästa tal som inte är utstruket är ett primtal.
  4. Stryk ut alla tal, som är både större än det primtalet du hittade i föregående steget och multiplar av det.
  5. Upprepa stegen 3 och 4 tills du har nått ett nummer som är större än kvadratroten av n (det största talet i listan).
  6. Alla kvarstående tal i listan är primtal.

Se även[redigera | redigera wikitext]

Externa länkar[redigera | redigera wikitext]

Referenser[redigera | redigera wikitext]