Prime Number Checker

Paano gamitin ang prime number checker

1. Mag-type ng Buong numero. Tinatanggap din ang mga expression: 2^61-1, 10^12+39, 20!+1 o 3711.
2. Lumalabas ang sagot habang nagta-type ka; pindutin ang Suriin para bigyan ng mas mahabang oras ang factorization ng mahirap na numero.
3. Basahin ang hatol, ang Prime factorization, ang Bilang ng divisor, ang Naunang prime at ang Susunod na prime. Ipinapaliwanag ng panel na Bakit kung paano nakuha ang sagot, at kinokopya ng Kopyahin ang factorization ang product ng mga prime.
4. Para maglista ng mga prime, punan ang Mula at Hanggang sa ilalim ng Mga prime number sa isang saklaw at pindutin ang Ilista ang mga prime.

Tinatanggap ang mga numerong hanggang 2048 bit (mga 617 digit), at lahat ay tumatakbo sa iyong browser.

Ano ang prime number

Ang prime number ay buong numerong higit sa 1 na ang tanging divisor ay 1 at ang sarili nito: 2, 3, 5, 7, 11, 13… Ang numerong may iba pang divisor ay composite, at maisusulat ito sa isang paraan lang bilang product ng mga prime, ang prime factorization nito (360 = 2³ × 3² × 5). Hindi prime at hindi composite ang 0 at 1, at ang 2 lang ang even na prime.

Makukuha ang bilang ng divisor mula sa factorization: dagdagan ng 1 ang bawat exponent at i-multiply ang lahat. Ang 360 = 2³ × 3² × 5 ay may (3 + 1)(2 + 1)(1 + 1) = 24 divisor. Laging eksaktong 2 ang divisor ng isang prime.

Paano gumagana ang pagsusuri

• Maliliit na numero (mas mababa sa isang milyon) ay sinusuri sa pamamagitan ng trial division: kung walang prime hanggang sa square root nito ang naghahati sa numero, prime ito. Hindi na kailangang lumampas pa, dahil ang composite na numero ay laging may factor na hindi lalampas sa square root nito.
• Mas malalaking numero ay unang hinahati sa bawat prime na mas mababa sa 1000, saka ipinapasa sa Miller–Rabin test. Sa 13 base na 2, 3, 5, …, 41, napatunayang eksakto ang test na ito para sa bawat numerong mas mababa sa 3.3 × 10²⁴, kasama ang lahat ng 64-bit na integer. Sigurado ang sagot para sa mga numerong iyon.
• Sa itaas ng 3.3 × 10²⁴, 25 base ang ginagamit at ang numerong pumasa sa lahat ay iniuulat bilang probable prime. Mas mababa sa 1 sa 10¹⁵ ang tsansa ng pagkakamali, pero hindi ito matematikal na patunay. Kapag bumagsak ang test, tiyak na composite ang numero.

Paano ginagawa ang factorization

Natutuklasan ang maliliit na factor sa pamamagitan ng trial division. Ang mas malalaking composite na bahagi ay hinahati gamit ang Pollard’s rho algorithm (variant ni Brent), na nakakahanap ng mga factor na hanggang humigit-kumulang 10 digit sa loob ng isang saglit. Ang mas mahihirap na numero, tulad ng product ng dalawang prime na may 15 digit o higit pa, ay maaaring tumagal nang lampas sa anumang time limit, kaya humihinto ang factoring pagkalipas ng ilang segundo. Mamarkahan ang huling factor bilang composite pero hindi nahati, at kapag pinindot muli ang Suriin, bibigyan ito ng mas mahabang oras.

Mga prime sa isang saklaw

Gumagamit ang listahan ng saklaw ng segmented sieve of Eratosthenes, na nagkukros ng mga multiple ng bawat prime. Tumatanggap ito ng hanggang 1,000,000 numero kada saklaw, na may pinakamataas na hangganang hanggang 10¹². Sakop ng bilang ang buong saklaw, at inililista ang unang 2,000 prime. Halimbawa, may 25 prime sa pagitan ng 1 at 100, at 78,498 sa ibaba ng isang milyon.