Om Eratosthenes' si - sådan virker primtalssien

Eratosthenes fra Kyrene

Eratosthenes levede fra omkring 276 til 194 f.Kr. og var leder af det store bibliotek i Alexandria. Han er mest kendt for at have målt Jordens størrelse ud fra længden af skygger i to byer. Sien er opkaldt efter ham, fordi Nikomachos fra Gerasa beskrev den som hans metode i Introduktion til aritmetikken, skrevet omkring år 100 e.Kr.

Sådan virker sien

Skriv tallene fra 2 til N. Det første tal, 2, er et primtal: stryg 4, 6, 8 og alle andre multipla af 2. Det næste tal, der er tilbage, 3, er et primtal: stryg 9, 12, 15 og så videre. Fortsæt med 5, 7 og de næste tal, der er tilbage. Et tal, der aldrig bliver streget ud, har ingen mindre faktor, så det er et primtal.

Stop ved kvadratroden

Hvert sammensat tal op til N har en primfaktor, der ikke er større end kvadratroden af N. Så snart p² er større end N, er der altså intet mere at stryge. For primtallene op til 100 behøver du kun 2, 3, 5 og 7, og for 1000 primtallene op til 31.

Hvor hurtig er den?

Sien bruger omkring N log log N trin, hvilket kun vokser lidt hurtigere end N selv. Computere bruger den stadig, ofte i stykker som en segmenteret si, til at liste primtal op til milliarder. Til at teste, om ét stort tal er et primtal, er andre metoder hurtigere.

Ofte stillede spørgsmål

Hvem opfandt Eratosthenes' si?

Den er opkaldt efter Eratosthenes fra Kyrene, en græsk lærd fra det tredje århundrede f.Kr. Den ældste skriftlige beskrivelse er af Nikomachos fra Gerasa, omkring år 100 e.Kr.

Hvorfor begynder sien at stryge ved p²?

Hvert mindre multiplum af p har en mindre primfaktor, så et mindre primtal har allerede streget det ud.

Hvor mange primtal er der under 1000?

Der er 168 primtal under 1000. Det største er 997.