Verificare număr prim

Ce e un număr prim

Un număr natural mai mare decât 1 care se împarte exact doar la 1 și la el însuși: 2, 3, 5, 7, 11… Orice alt număr mai mare decât 1 e compus și se scrie, într-un singur fel, ca produs de numere prime: 2026 = 2 × 1013. 0 și 1 nu sunt nici prime, nici compuse.

Cum verifică

Întâi împarte la numerele prime mai mici decât 1000. Apoi face testul Miller–Rabin pe bazele 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 și 41: cel mai mic număr compus care le trece pe toate 13 este 3.317.044.064.679.887.385.961.981 (șirul A014233 din enciclopedia de șiruri OEIS), deci pentru numerele mai mici răspunsul e sigur.

Peste el, numărul mai trece prin 20 de baze alese la întâmplare. Dacă le trece pe toate, unealta îl numește probabil prim: n-a găsit nicio dovadă că e compus, dar nici n-a dovedit că e prim.

Descompunerea în factori

Unealta împarte la numerele prime de până la 100.000, apoi caută factorii mari cu metoda rho a lui Pollard, în varianta lui Brent, un număr limitat de pași, ca pagina să nu se blocheze. Un factor prea mare pentru pașii aceia rămâne scris între paranteze: e sigur compus, dar nedescompus.

Numerele prime de dinainte și de după sunt găsite cu același test, număr cu număr.

Nimic nu pleacă din browser

Calculul se face în browserul tău; numărul scris nu e trimis nicăieri.