Algarvu kontroll

Kuidas algarvu kontrolli kasutada

1. Sisesta Täisarv. Avaldised sobivad samuti: 2^61-1, 10^12+39, 20!+1 või 3711.
2. Vastus ilmub sisestamise ajal; vajuta Kontrolli, et anda raske arvu algteguriteks lahutamisele rohkem aega.
3. Loe vastust, Algtegurite lahutust, Jagajate arvu, Eelmist algarvu ja Järgmist algarvu. Paneel Miks selgitab, kuidas vastuseni jõuti, ning Kopeeri algtegurid kopeerib algarvude korrutise.
4. Algarvude loetlemiseks täida jaotises Algarvud vahemikus väljad Alates ja Kuni ning vajuta Loetle algarvud.

Lubatud on arvud kuni 2048 bitti (umbes 617 numbrit) ja kõik töötab sinu brauseris.

Mis teeb arvust algarvu

Algarv on täisarv, mis on suurem kui 1 ja mille ainsad jagajad on 1 ja ta ise: 2, 3, 5, 7, 11, 13… Arvu, millel on teisi jagajaid, nimetatakse kordarvuks ning seda saab täpselt ühel viisil kirjutada algarvude korrutisena, ehk algtegurite lahutusena (360 = 2³ × 3² × 5). Arvud 0 ja 1 ei ole ei algarvud ega kordarvud ning 2 on ainus paarisalgarv.

Jagajate arv tuleneb algtegurite lahutusest: liida igale astendajale 1 ja korruta. Arvul 360 = 2³ × 3² × 5 on (3 + 1)(2 + 1)(1 + 1) = 24 jagajat. Algarvul on alati täpselt 2.

Kuidas test töötab

• Väikesed arvud (alla miljoni) kontrollitakse katsejagamisega: kui ükski algarv kuni ruutjuureni arvu ei jaga, on see algarv. Kaugemale minna pole vaja, sest kordarvul on alati tegur, mis ei ole ruutjuurest suurem.
• Suuremad arvud jagatakse esmalt kõigi algarvudega alla 1000 ja seejärel lastakse läbi Miller–Rabini testi. 13 alusega 2, 3, 5, …, 41 on see test tõestatult täpne kõigi arvude puhul alla 3,3 × 10²⁴, kuhu kuuluvad kõik 64-bitised täisarvud. Nende arvude puhul on vastus kindel.
• Üle 3,3 × 10²⁴ kasutatakse 25 alust ja arv, mis need kõik läbib, märgitakse tõenäoliseks algarvuks. Vea tõenäosus on alla 1 : 10¹⁵, kuid see ei ole matemaatiline tõestus. Kui test ebaõnnestub, on arv kindlasti kordarv.

Kuidas arve teguriteks lahutatakse

Väikesed tegurid leitakse katsejagamisega. Suuremad kordarvu osad jagatakse Pollardi rho algoritmiga (Brenti variant), mis leiab kuni umbes 10-kohalised tegurid murdosa sekundiga. Raskemad arvud, näiteks kahe vähemalt 15-kohalise algarvu korrutis, võivad võtta palju kauem kui mis tahes ajapiirang, seega lõpetab tööriist teguriteks lahutamise mõne sekundi pärast. Viimane tegur märgitakse siis kordarvuks, mida ei jagatud, ja Kontrolli uuesti vajutamine annab sellele rohkem aega.

Algarvud vahemikus

Vahemiku loend kasutab segmenteeritud Eratosthenese sõela, mis kriipsutab maha iga algarvu kordsed. Lubatud on kuni 1 000 000 arvu vahemiku kohta ning ülempiir kuni 10¹². Loendus hõlmab kogu vahemikku ja loetletakse esimesed 2000 algarvu. Näiteks arvude 1 ja 100 vahel on 25 algarvu ja alla miljoni 78 498.