Verificare număr prim și descompunere în factori

Un număr prim este un număr natural mai mare decât 1 care nu are alți divizori pozitivi în afară de 1 și de el însuși. Primele numere prime sunt 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... 2 este singurul număr prim par: orice alt număr par se împarte la 2, deci este compus. Asta îl face pe 2 unic printre numerele prime. Cum verifici dacă un număr este prim: este suficient să verifici divizibilitatea cu numerele prime până la rădăcina lui pătrată. Pentru a testa 97, verifici 2, 3, 5 și 7 (√97 ≈ 9,8). Dacă niciunul nu îl împarte exact, numărul este prim. Există o infinitate de numere prime: Euclid a demonstrat acest lucru în jurul anului 300 î.Hr. Cel mai mare număr prim cunoscut (în 2024) are peste 40 de milioane de cifre. De ce contează numerele prime: criptarea RSA (care protejează internet bankingul, e-mailul și HTTPS) se bazează pe faptul că înmulțirea a două numere prime mari este ușoară, dar descompunerea rezultatului înapoi în factori primi este practic imposibilă din punct de vedere computațional.