Alkulukulaskin

Näin käytät alkulukulaskinta

1. Kirjoita Kokonaisluku. Myös lausekkeet kelpaavat: 2^61-1, 10^12+39, 20!+1 tai 3711.
2. Vastaus ilmestyy kirjoittaessasi. Paina Tarkista, jos haluat antaa vaikealle luvulle lisää aikaa tekijöihin jakoon.
3. Lue tulos, Alkutekijähajotelma, Tekijöiden määrä, Edellinen alkuluku ja Seuraava alkuluku. Perustelu-osio selittää, miten vastaukseen päädyttiin, ja Kopioi alkutekijähajotelma kopioi alkulukujen tulon.
4. Jos haluat luetella alkulukuja, täytä kohdassa Alkuluvut välillä kentät Alkaen ja Asti ja paina Luettele alkuluvut.

Työkalu hyväksyy luvut 2048 bittiin asti (noin 617 numeroa), ja kaikki laskenta tapahtuu selaimessasi.

Mikä tekee luvusta alkuluvun

Alkuluku on kokonaisluku, joka on suurempi kuin 1 ja jonka ainoat tekijät ovat 1 ja luku itse: 2, 3, 5, 7, 11, 13 … Luku, jolla on muitakin tekijöitä, on yhdistetty luku, ja se voidaan kirjoittaa täsmälleen yhdellä tavalla alkulukujen tuloksi eli alkutekijähajotelmaksi (360 = 2³ × 3² × 5). Luvut 0 ja 1 eivät ole alkulukuja eivätkä yhdistettyjä lukuja, ja 2 on ainoa parillinen alkuluku.

Tekijöiden määrä seuraa hajotelmasta: lisää jokaiseen eksponenttiin 1 ja kerro keskenään. Luvulla 360 = 2³ × 3² × 5 on (3 + 1)(2 + 1)(1 + 1) = 24 tekijää. Alkuluvulla niitä on aina täsmälleen 2.

Miten testi toimii

• Pienet luvut (alle miljoona) tarkistetaan koejaolla: jos mikään neliöjuureen asti oleva alkuluku ei jaa lukua, se on alkuluku. Pidemmälle ei tarvitse mennä, koska yhdistetyllä luvulla on aina tekijä, joka ei ole neliöjuurta suurempi.
• Suuremmat luvut jaetaan ensin kaikilla alle 1000 olevilla alkuluvuilla ja ajetaan sitten Miller–Rabin-testin läpi. Kolmentoista kantaluvun 2, 3, 5, …, 41 joukolla testi on todistettu tarkaksi kaikille alle 3,3 × 10²⁴ luvuille, mukaan lukien kaikki 64-bittiset kokonaisluvut. Näille luvuille vastaus on varma.
• Yli 3,3 × 10²⁴ luvuilla käytetään 25 kantalukua, ja luku, joka läpäisee ne kaikki, ilmoitetaan todennäköiseksi alkuluvuksi. Virheen todennäköisyys on alle 1 / 10¹⁵, mutta kyse ei ole matemaattisesta todistuksesta. Jos testi epäonnistuu, luku on varmasti yhdistetty.

Miten luvut jaetaan tekijöihin

Pienet tekijät löydetään koejaolla. Suuremmat yhdistetyt osat jaetaan Pollardin rho -algoritmilla (Brentin muunnelma), joka löytää jopa noin 10-numeroiset tekijät sekunnin murto-osassa. Vaikeammat luvut, kuten kahden vähintään 15-numeroisen alkuluvun tulo, voivat viedä paljon pidempään kuin mikään aikaraja sallii, joten tekijöihin jako keskeytyy muutaman sekunnin jälkeen. Viimeinen tekijä merkitään silloin yhdistetyksi mutta jakamattomaksi, ja uusi Tarkista-painallus antaa sille lisää aikaa.

Alkuluvut välillä

Välin luettelo käyttää segmentoitua Eratostheneen seulaa, joka yliviivaa kunkin alkuluvun monikerrat. Se hyväksyy enintään 1 000 000 lukua väliä kohden, ja yläraja voi olla enintään 10¹². Lukumäärä koskee koko väliä, ja ensimmäiset 2 000 alkulukua luetellaan. Esimerkiksi lukujen 1 ja 100 välillä on 25 alkulukua ja alle miljoonan niitä on 78 498.