Eratosthenes' såld

Eratosthenes' såld (eller sil) er en algoritme for å finne alle primtall opp til et visst tall n (for eksempel 100).

Skriv opp alle heltallene til og med n (for eksempel 100).
Stryk over alle tallene i 2-gangen, bortsett fra 2.
Stryk over alle tallene i 3-gangen, bortsett fra 3.
Alle tallene i 4-gangen er allerede strøket over.
Stryk over alle tallene i 5-gangen, bortsett fra 5.
osv.

Det holder å fortsette til man har kommet til $\sqrt{n}$-gangen (for eksempel 10-gangen, hvis n=100).

Alle tallene som nå står igjen (bortsett fra 1) er primtall.

Undervisningsopplegg

Primtallsfaktorisering - Eratosthenes' såld og terningspill

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License