Eratosthenes såll

Från Rilpedia

Texten från svenska Wikipedia

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 ^[1].

Algoritmen

Fel vid skapande av miniatyrbild: Ogiltiga parametrar för miniatyrbilden

Eratosthenes såll på talen 2-120.

Sållen 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 utstruken ä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 de 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

Referenser

1. ↑ The Prime Glossary: "The Sieve of Eratosthenes", http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes, hänvisning från 16. November 2008.