Om Eratosthenes såll - så fungerar primtalssållet

Eratosthenes från Kyrene

Eratosthenes levde ungefär 276 till 194 f.Kr. och var chef för det stora biblioteket i Alexandria. Han är mest känd för att ha mätt jordens storlek utifrån längden på skuggor i två städer. Sållet är uppkallat efter honom eftersom Nikomachos från Gerasa beskrev det som hans metod i Introduktion till aritmetiken, skriven omkring år 100 e.Kr.

Så fungerar sållet

Skriv talen från 2 till N. Det första talet, 2, är ett primtal: stryk 4, 6, 8 och varje annan multipel av 2. Nästa tal som är kvar, 3, är ett primtal: stryk 9, 12, 15 och så vidare. Fortsätt med 5, 7 och nästa tal som är kvar. Ett tal som aldrig stryks har ingen mindre faktor, så det är ett primtal.

Sluta vid kvadratroten

Varje sammansatt tal upp till N har en primfaktor som inte är större än kvadratroten ur N. Så snart p² är större än N finns det alltså inget mer att stryka. För primtalen upp till 100 behöver du bara 2, 3, 5 och 7, och för 1000 primtalen upp till 31.

Hur snabbt är det?

Sållet tar ungefär N log log N steg, vilket bara växer lite snabbare än N självt. Datorer använder det fortfarande, ofta i delar som ett segmenterat såll, för att lista primtal upp till miljarder. För att testa om ett enda stort tal är ett primtal är andra metoder snabbare.

Ofta ställda frågor

Vem uppfann Eratosthenes såll?

Det är uppkallat efter Eratosthenes från Kyrene, en grekisk lärd från 200-talet f.Kr. Den äldsta skrivna beskrivningen är av Nikomachos från Gerasa, omkring år 100 e.Kr.

Varför börjar sållet stryka vid p²?

Varje mindre multipel av p har en mindre primfaktor, så ett mindre primtal har redan strukit den.

Hur många primtal finns det under 1000?

Det finns 168 primtal under 1000. Det största är 997.