Eratosthenes såll

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

Eratosthenes såll på talen 2–10. Här uppdelat i steg för att visa vad som händer.

Algoritmen

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 heltal 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 steg 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

• Primtalssatsen
• Aritmetikens fundamentalsats

Externa länkar

• primes.utm.edu
• mathworld.wolfram.com