Eratosthenes såll

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2023-07) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

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

Algoritmen

(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