Primtalskontroll

Så använder du primtalskontrollen

1. Skriv ett Heltal. Uttryck accepteras också: 2^61-1, 10^12+39, 20!+1 eller 3711.
2. Svaret visas medan du skriver. Tryck på Kontrollera för att ge faktoriseringen mer tid för ett svårt tal.
3. Läs av beskedet, Primfaktorisering, Antal delare, Föregående primtal och Nästa primtal. Panelen Varför förklarar hur svaret nåddes, och Kopiera faktoriseringen kopierar produkten av primtal.
4. Vill du lista primtal fyller du i Från och Till under Primtal i ett intervall och trycker på Lista primtal.

Tal upp till 2048 bitar (cirka 617 siffror) accepteras, och allt körs i din webbläsare. Inget du skriver in skickas till en server.

Vad som gör ett tal till ett primtal

Ett primtal är ett heltal större än 1 vars enda delare är 1 och talet självt: 2, 3, 5, 7, 11, 13 … Ett tal med andra delare är sammansatt, och det kan skrivas på exakt ett sätt som en produkt av primtal, sin primfaktorisering (360 = 2³ × 3² × 5). Talen 0 och 1 är varken primtal eller sammansatta, och 2 är det enda jämna primtalet.

Antalet delare följer av faktoriseringen: addera 1 till varje exponent och multiplicera. 360 = 2³ × 3² × 5 har (3 + 1)(2 + 1)(1 + 1) = 24 delare. Ett primtal har alltid exakt 2.

Så fungerar testet

• Små tal (under en miljon) kontrolleras med provdivision: om inget primtal upp till kvadratroten delar talet är det ett primtal. Man behöver inte gå längre, eftersom ett sammansatt tal alltid har en faktor som inte är större än kvadratroten.
• Större tal delas först med varje primtal under 1000 och körs sedan genom Miller–Rabin-testet. Med de 13 baserna 2, 3, 5, …, 41 har testet bevisats exakt för alla tal under 3,3 × 10²⁴, vilket omfattar alla 64-bitars heltal. För de talen är svaret säkert.
• Över 3,3 × 10²⁴ används 25 baser, och ett tal som klarar dem alla rapporteras som ett troligt primtal. Risken för fel är mindre än 1 på 10¹⁵, men det är inget matematiskt bevis. När testet misslyckas är talet säkert sammansatt.

Så faktoriseras tal

Små faktorer hittas med provdivision. Större sammansatta delar delas upp med Pollards rho-algoritm (Brents variant), som hittar faktorer på upp till cirka 10 siffror på en bråkdel av en sekund. Svårare tal, till exempel produkten av två primtal på 15 siffror eller mer, kan ta mycket längre tid än någon tidsgräns, så faktoriseringen avbryts efter några sekunder. Den sista faktorn markeras då som sammansatt men inte uppdelad, och om du trycker på Kontrollera igen får den mer tid.

Primtal i ett intervall

Intervalllistan använder en segmenterad Eratosthenes såll, som stryker multiplerna av varje primtal. Den accepterar upp till 1 000 000 tal per intervall med en övre gräns upp till 10¹². Antalet gäller hela intervallet, och de första 2 000 primtalen listas. Det finns till exempel 25 primtal mellan 1 och 100 och 78 498 under en miljon.