Kalkulator prostogo chysla

Proste chyslo — tse naturalne chyslo, bilshe za 1, yake dilitsa lyshe na 1 ta na sebe same. Pryklady: 2, 3, 5, 7, 11, 13, 17, 19. Chyslo 2 — yedyne parne proste chyslo. Chysla 4, 6, 9, 15 ne ye prostymi, bo mayut inshi dilnyky.

Nayprostishyy sposib — probne dilennya: dilite chyslo n na vsi tsilochyslovi znachennya vid 2 do korenyа kvadratnoho z n. Yaksho zhoden z nykh ne ye dilnykom — chyslo proste. Dlya n=17 pereviryyemo do √17 ≈ 4,1 — zhoден z 2, 3, 4 ne dili 17, otzhe 17 proste.

Naybilshe vidome proste chyslo (stanom na 2024 rik) — chyslo Mersenna 2^136 279 841 − 1, viyavlene proektom GIMPS. Vono maye ponad 41 milion tsyfr. Poshuk dedali bilshykh prostykh chysel — aktyvna haluz matematyky ta informatyky.

Evklid doviv blyzko 300 r. do n.e., shcho prostykh chysel neskinchenno bahato. Teorema pro prosti chysla stverdzhuye, shcho kilkist prostykh chysel, menshykh za n, pryblyzno dorivnyuye n / ln(n). Do 1000 yikh 168, do 1 000 000 — azhz 78 498.

Kozhe naturalne chyslo, bilshe za 1, mozhna yedynym sposobom (z tochnistyu do poryadku) zapysaty yak dobutok prostykh chysel. Napryklad: 12 = 2 × 2 × 3, 30 = 2 × 3 × 5, 100 = 2 × 2 × 5 × 5. Tse nazyvayet sya osnovnoyu teor emoyu aryfmetyky.

Resheto Eratosthena — tse starodavniy alhorytm dlya znahodzhennya vsikh prostykh chysel do zadenoyi mezhi. Pochynayemo vid 2 i vykresluyemo vsi yoho kratni; potim perekhodymo do nastupnoho nevykreslkenoho chysla i povtoryuyemo. Nevykresleni chysla — prosti. Metod efektyvnyy dlya mezh do kilkokh milioniv.

Ni — 1 ne ye prostym chyslom. Istorychno yoho inodi vklyuchaly, ale suchasne vyznachennya vyklyuchaye 1, bo yiyi vklyuchennya porushuvalo b osnovnu teoremu aryfmetyky (rozklady ne buly by yedynymy: napryklad 6 = 2×3 = 2×3×1 = 2×3×1×1…).

Chysla-blyznyuky — tse pary prostykh chysel, yaki vidriznyayutsya na 2: napryklad (3, 5), (11, 13), (17, 19), (29, 31). Hipoteza pro chysla-blyznyuky stverdzhuye, shcho takykh par neskinchenno bahato, ale vona dosy ne dovedena — odna z velykykh vidkrytykh zadach matematyky.

Prosti chysla — osnova kryptohrafiyi. Alhorytm RSA hruntuyet sya na skladnosti rozkladu velykykh chysel na prosti mnozhnyky. Kryptohrafichni klyuchi zavdovzhky 2048–4096 bitiv — tse dobutky dvokh velych eznykh prostykh chysel. Bez prostykh chysel bezpechna internet-komunikatsiya bula b nemozhlyvоyu.

Kalkulator vykorystovuye probne dilennya do √n. Dlya n = 10^9 = 1 000 000 000 vin perevirya ye do ~31 623 dilnykiv — tse duze shvydko. Dlya nabahato bilshykh chysel zastosvuyutsya imovirnisni testy (Miller-Rabin) abo deterministychni (AKS), ale probne dilennya tsilkom pidkhodi t dlya navchalnych tsil.