Pirmskaitļu pārbaude

Kā lietot pirmskaitļu pārbaudi

1. Ierakstiet Vesels skaitlis. Der arī izteiksmes: 2^61-1, 10^12+39, 20!+1 vai 3711.
2. Atbilde parādās rakstot; nospiediet Pārbaudīt, lai grūtam skaitlim dotu sadalīšanai vairāk laika.
3. Izlasiet slēdzienu, Sadalījums pirmreizinātājos, Dalītāju skaits, Iepriekšējais pirmskaitlis un Nākamais pirmskaitlis. Panelis Kāpēc izskaidro, kā atbilde iegūta, bet Kopēt sadalījumu nokopē pirmskaitļu reizinājumu.
4. Lai uzskaitītu pirmskaitļus, aizpildiet No un Līdz sadaļā Pirmskaitļi intervālā un nospiediet Uzskaitīt pirmskaitļus.

Tiek pieņemti skaitļi līdz 2048 bitiem (apmēram 617 cipari), un viss notiek jūsu pārlūkprogrammā. Nekas, ko ievadāt, netiek sūtīts uz serveri.

Kas padara skaitli par pirmskaitli

Pirmskaitlis ir vesels skaitlis, kas lielāks par 1 un kuram ir tikai divi dalītāji – 1 un pats skaitlis: 2, 3, 5, 7, 11, 13… Skaitli ar citiem dalītājiem sauc par saliktu skaitli, un to var uzrakstīt tieši vienā veidā kā pirmskaitļu reizinājumu – tā sadalījumu pirmreizinātājos (360 = 2³ × 3² × 5). Skaitļi 0 un 1 nav ne pirmskaitļi, ne salikti skaitļi, un 2 ir vienīgais pāra pirmskaitlis.

Dalītāju skaitu var iegūt no sadalījuma: katram kāpinātājam pieskaita 1 un rezultātus sareizina. Skaitlim 360 = 2³ × 3² × 5 ir (3 + 1)(2 + 1)(1 + 1) = 24 dalītāji. Pirmskaitlim vienmēr ir tieši 2.

Kā darbojas pārbaude

• Mazus skaitļus (līdz vienam miljonam) pārbauda ar mēģinājuma dalīšanu: ja neviens pirmskaitlis līdz kvadrātsaknei skaitli nedala, tas ir pirmskaitlis. Tālāk meklēt nav vajadzības, jo salikta skaitļa mazākais dalītājs nepārsniedz tā kvadrātsakni.
• Lielākus skaitļus vispirms dala ar katru pirmskaitli līdz 1000, pēc tam veic Millera–Rabina testu. Ar 13 bāzēm 2, 3, 5, …, 41 šis tests ir pierādīti precīzs visiem skaitļiem līdz 3,3 × 10²⁴, kas ietver visus 64 bitu veselos skaitļus. Šādiem skaitļiem atbilde ir droša.
• Virs 3,3 × 10²⁴ izmanto 25 bāzes, un skaitlis, kas iztur tās visas, tiek uzrādīts kā iespējams pirmskaitlis. Kļūdas iespēja ir mazāka par 1 pret 10¹⁵, taču tas nav matemātisks pierādījums. Ja tests izgāžas, skaitlis noteikti ir salikts.

Kā skaitļus sadala reizinātājos

Mazus reizinātājus atrod ar mēģinājuma dalīšanu. Lielākas saliktas daļas sadala ar Polarda rho algoritmu (Brenta variantu), kas atrod līdz aptuveni 10 ciparu garus reizinātājus sekundes daļā. Grūtāki skaitļi, piemēram, divu vismaz 15 ciparu pirmskaitļu reizinājums, var prasīt daudz ilgāku laiku nekā jebkurš laika ierobežojums, tāpēc sadalīšana pēc dažām sekundēm apstājas. Pēdējais reizinātājs tad tiek atzīmēts kā salikts, bet nesadalīts, un, vēlreiz nospiežot Pārbaudīt, tas saņem vairāk laika.

Pirmskaitļi intervālā

Intervāla saraksts izmanto segmentētu Eratostena sietu, kas izsvītro katra pirmskaitļa daudzkārtņus. Tas pieņem līdz 1 000 000 skaitļu intervālā ar augšējo robežu līdz 10¹². Skaits aptver visu intervālu, bet tiek uzskaitīti pirmie 2000 pirmskaitļi. Piemēram, starp 1 un 100 ir 25 pirmskaitļi, bet zem miljona – 78 498.