Pirminių skaičių tikrintuvas

Kaip naudotis pirminių skaičių tikrintuvu

1. Įvesk Sveikasis skaičius. Tinka ir reiškiniai: 2^61-1, 10^12+39, 20!+1 arba 3711.
2. Atsakymas rodomas, kai tik rašai. Spausk Tikrinti, jei sunkiam skaičiui nori duoti daugiau laiko skaidymui.
3. Perskaityk išvadą, Skaidymas pirminiais dauginamaisiais, Daliklių skaičius, Ankstesnis pirminis skaičius ir Kitas pirminis skaičius. Skydelis Kodėl paaiškina, kaip gautas atsakymas, o Kopijuoti skaidinį nukopijuoja pirminių skaičių sandaugą.
4. Jei nori išvardyti pirminius skaičius, skiltyje Pirminiai skaičiai intervale užpildyk Nuo ir Iki ir spausk Išvardyti pirminius.

Priimami skaičiai iki 2048 bitų (apie 617 skaitmenų), o viskas veikia tavo naršyklėje. Nieko, ką įvedi, nesiunčiame į serverį.

Kas daro skaičių pirminiu

Pirminis skaičius yra sveikasis skaičius, didesnis už 1, kurio vieninteliai dalikliai yra 1 ir jis pats: 2, 3, 5, 7, 11, 13… Skaičius, turintis kitų daliklių, yra sudėtinis, ir jį galima vieninteliu būdu užrašyti kaip pirminių skaičių sandaugą – tai jo skaidinys pirminiais dauginamaisiais (360 = 2³ × 3² × 5). Skaičiai 0 ir 1 nėra nei pirminiai, nei sudėtiniai, o 2 yra vienintelis lyginis pirminis skaičius.

Daliklių skaičių galima rasti iš skaidinio: prie kiekvieno laipsnio rodiklio pridėk 1 ir sudaugink. 360 = 2³ × 3² × 5 turi (3 + 1)(2 + 1)(1 + 1) = 24 daliklius. Pirminis skaičius visada turi lygiai 2.

Kaip veikia testas

• Maži skaičiai (iki milijono) tikrinami bandomuoju dalijimu: jei nė vienas pirminis skaičius iki kvadratinės šaknies jo nedalija, jis pirminis. Toliau eiti nereikia, nes sudėtinis skaičius visada turi daliklį, ne didesnį už savo kvadratinę šaknį.
• Didesni skaičiai pirmiausia dalijami iš visų pirminių skaičių, mažesnių už 1000, o tada tikrinami Millerio ir Rabino testu. Su 13 bazių 2, 3, 5, …, 41 šis testas įrodytai tikslus kiekvienam skaičiui, mažesniam už 3,3 × 10²⁴, o tai apima visus 64 bitų sveikuosius skaičius. Šiems skaičiams atsakymas tikras.
• Viršijus 3,3 × 10²⁴, naudojama 25 bazės, ir skaičius, išlaikęs jas visas, pateikiamas kaip tikėtinai pirminis. Klaidos tikimybė mažesnė nei 1 iš 10¹⁵, tačiau tai nėra matematinis įrodymas. Kai testas neišlaikomas, skaičius tikrai sudėtinis.

Kaip skaidomi skaičiai

Mažus daliklius randa bandomasis dalijimas. Didesnės sudėtinės dalys skaidomos Pollardo rho algoritmu (Brento variantu), kuris per sekundės dalį randa iki maždaug 10 skaitmenų daliklius. Sunkesni skaičiai, pavyzdžiui, dviejų 15 ar daugiau skaitmenų pirminių skaičių sandauga, gali užtrukti gerokai ilgiau nei bet kuri laiko riba, todėl skaidymas sustoja po kelių sekundžių. Tada paskutinis dauginamasis pažymimas kaip sudėtinis, bet nesuskaidytas, o dar kartą paspaudus Tikrinti jam skiriama daugiau laiko.

Pirminiai skaičiai intervale

Intervalo sąrašui sudaryti naudojamas segmentuotas Eratosteno rėtis, kuris išbraukia kiekvieno pirminio skaičiaus kartotinius. Leidžiama iki 1 000 000 skaičių viename intervale, viršutinė riba iki 10¹². Skaičius apima visą intervalą, o išvardijama pirmųjų 2000 pirminių skaičių. Pavyzdžiui, nuo 1 iki 100 yra 25 pirminiai skaičiai, o iki milijono – 78 498.