Test prvočísel a rozklad na prvočinitele

Prvočíslo je prirodzené číslo väčšie ako 1, ktoré nemá iných kladných deliteľov okrem 1 a samého seba. Prvými prvočíslami sú 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... 2 je jediné párne prvočíslo: každé iné párne číslo je deliteľné 2, a teda je zložené. Preto je 2 medzi prvočíslami výnimočná. Ako overiť, či je číslo prvočíslo: stačí skúšať deliteľnosť prvočíslami až po jeho druhú odmocninu. Pri teste čísla 97 vyskúšajte 2, 3, 5, 7 (√97 ≈ 9,8). Ak ho žiadne z nich nedelí bezo zvyšku, ide o prvočíslo. Prvočísel je nekonečne veľa: Euklides okolo roku 300 pred n. l. dokázal, že prvočísel je nekonečne veľa. Najväčšie známe prvočíslo (k roku 2024) má viac ako 40 miliónov číslic. Prečo sú prvočísla dôležité: šifrovanie RSA (zabezpečenie internetového bankovníctva, e-mailu, HTTPS) stojí na tom, že vynásobiť dve veľké prvočísla je ľahké, ale rozložiť výsledok späť na prvočinitele je výpočtovo prakticky nerealizovateľné.