Sprawdzanie liczb pierwszych i rozkład na czynniki

Liczba pierwsza to liczba naturalna większa od 1, która nie ma innych dodatnich dzielników niż 1 i ona sama. Pierwsze liczby pierwsze to 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... 2 to jedyna parzysta liczba pierwsza: każda inna liczba parzysta dzieli się przez 2, więc jest złożona. To czyni dwójkę wyjątkową wśród liczb pierwszych. Jak sprawdzić, czy liczba jest pierwsza: wystarczy sprawdzić podzielność przez liczby pierwsze nie większe od jej pierwiastka kwadratowego. Aby przetestować 97, sprawdź 2, 3, 5 i 7 (√97 ≈ 9,8). Jeśli żadna z nich nie dzieli 97 bez reszty, liczba jest pierwsza. Liczb pierwszych jest nieskończenie wiele: Euklides udowodnił to około 300 roku p.n.e. Największa znana liczba pierwsza (stan na 2024 rok) ma ponad 40 milionów cyfr. Dlaczego liczby pierwsze są ważne: szyfrowanie RSA (chroniące bankowość internetową, e-maile i HTTPS) opiera się na tym, że pomnożenie dwóch dużych liczb pierwszych jest łatwe, ale rozłożenie wyniku z powrotem na czynniki pierwsze jest praktycznie niewykonalne obliczeniowo.