Sjekk om et tall er et primtall, del det opp i primfaktorer, list opp alle primtall opptil N og finn det neste.
Et primtall har nøyaktig to divisorer, 1 og seg selv. Det gjør primtallene til aritmetikkens byggeklosser: hvert heltall over 1 er et produkt av primtall på nøyaktig én måte, og det er det aritmetikkens fundamentalteorem sier. 360 er 2³ × 3² × 5 og ingenting annet; 91 ser ut som et primtall, men er egentlig 7 × 13; 97 er derimot virkelig et primtall. Når faktoriseringen er kjent, følger andre fakta gratis — antall divisorer er produktet av hver eksponent pluss én, så 360 har (3 + 1) × (2 + 1) × (1 + 1) = 24 av dem.
Primtallssjekken her gjøres med prøvedivisjon, men bare opptil kvadratroten av tallet og bare mot kandidater på formen 6k ± 1, siden alt annet allerede er et multiplum av 2 eller 3. Det hopper over to tredeler av arbeidet og avgjør et tall under en billion på et par hundre tusen divisjoner, et par millisekunder. Over 10¹² blir selv det tregt i en nettleser, så svaret går over til den deterministiske Miller-Rabin-testen med basene 2 til 37, som er bevist eksakt for alle tall under 3,3×10²⁴ og dermed for alt dette verktøyet godtar, opptil 2⁵³ − 1. Å liste opp primtall bruker en annen klassiker: Eratosthenes' sil skriver ut hvert tall opptil N, beholder det minste umerkede, stryker ut alle multiplene av det og gjentar til bare primtallene står igjen.
Primtallsfaktorisering er maskineriet bak å forkorte brøker, finne MFM eller SFF og forenkle kvadratrøtter, og derfor læres det tidlig. Utenfor skolen er vanskeligheten med å faktorisere store tall det RSA-kryptering hviler på: å multiplisere to store primtall går på et blunk, å gjøre det om igjen gjør det ikke, og gapet mellom de to er hele sikkerhetsargumentet. Primtall tynnes også ut på forutsigbart vis når tallene vokser, men de tar aldri slutt — Euklid beviste det for over to tusen år siden. Tall opptil 2⁵³ − 1 kan testes her, faktorisering og nabo-primtallene fungerer opptil en billion, og primtallslisten går opptil 100 000. Ingenting du skriver inn, forlater nettleseren din.
Primtallssjekk med prøvedivisjon: n er et primtall når ingen heltall fra 2 opptil √n går opp i det, og det holder å teste 2, 3 og deretter hver kandidat på formen 6k ± 1. Faktorisering bruker de samme divisjonene og noterer hvor mange ganger hvert primtall går opp; antall divisorer er produktet av hver eksponent pluss én. Primtallslisten bruker Eratosthenes' sil. Over 10^12 kommer primtallssvaret fra den deterministiske Miller-Rabin-testen med basene 2 til 37, eksakt for alle tall under 2^53.
Prøv å dividere det med hvert primtall opptil kvadratroten: går ingen av dem opp, er tallet et primtall. For 97 er kvadratroten under 10, så det holder å teste 2, 3, 5 og 7 for å avgjøre det.
Nei. Et primtall må ha nøyaktig to ulike divisorer, og 1 har bare én. Å utelate det er også det som gjør primtallsfaktorisering entydig, siden ethvert tall ellers kunne fylles på med så mange 1-ere du vil.
Det er grunnlaget for å forkorte brøker, regne ut SFF og MFM, forenkle kvadratrøtter og telle divisorer. Å skrive 360 som 2³ × 3² × 5 gir umiddelbart de 24 divisorene og alt det deler med et annet tall.
Opptil 9 007 199 254 740 991 — det er 2⁵³ − 1 — for primtallssjekken. Faktorisering og nabo-primtallene går opptil 1 000 000 000 000, og primtallslisten opptil 100 000, slik at hvert svar kommer momentant i nettleseren.
Fordi alle andre partall er delelige med 2, noe som gir dem en tredje divisor og diskvalifiserer dem. Det er også derfor verktøyet hopper over partallskandidater når det først har testet 2.
Nei. Divisjonene, silen og Miller-Rabin-testen kjører alle i JavaScript på enheten din, uten kall til noen server og uten at noe lagres.
Vai.la gjør enhver URL om til en kortlenke med klikkstatistikk, QR Code og din egen biolink.
Vai.la er ikke ansvarlig for hvordan verktøyene brukes, eller for beslutninger tatt på grunnlag av resultatene.