Eratosthenes såll

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. Denna algoritm fungerar bra om det största talet som ska sållas inte är större än 10 miljoner .

Algoritmen

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

• Matematik
• Gaussiskt primtal
• Mersenneprimtal
• Primtalssatsen
• Perfekt tal
• Relativt prima
• Primtalstvilling
• Aritmetikens fundamentalsats

Externa länkar

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