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.

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]