Test prvočísel a rozklad na prvočinitele

Prvočíslo je přirozené číslo větší než 1, které nemá jiné kladné dělitele než 1 a samo sebe. Prvními prvočísly jsou 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... 2 je jediné sudé prvočíslo: každé jiné sudé číslo je dělitelné 2, a je tedy složené. Tím je 2 mezi prvočísly výjimečná. Jak ověřit, zda je číslo prvočíslo: stačí zkoušet dělitelnost prvočísly až do jeho druhé odmocniny. Pro test čísla 97 vyzkoušejte 2, 3, 5, 7 (√97 ≈ 9,8). Pokud žádné z nich číslo beze zbytku nedělí, jde o prvočíslo. Prvočísel je nekonečně mnoho: Eukleidés kolem roku 300 př. n. l. dokázal, že prvočísel je nekonečně mnoho. Největší známé prvočíslo (k roku 2024) má přes 40 milionů číslic. Proč jsou prvočísla důležitá: šifrování RSA (zabezpečení internetového bankovnictví, e-mailu, HTTPS) stojí na tom, že vynásobit dvě velká prvočísla je snadné, ale rozložit výsledek zpět na prvočinitele je výpočetně prakticky neproveditelné.