Primtalstjek og primfaktorisering

Et primtal er et naturligt tal større end 1, som ikke har andre positive divisorer end 1 og sig selv. De første primtal er 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... 2 er det eneste lige primtal: Alle andre lige tal er delelige med 2 og dermed sammensatte. Det gør 2 unikt blandt primtallene. Sådan tjekker du, om et tal er et primtal: Du behøver kun at teste delelighed med primtal op til kvadratroden. For at teste 97: tjek 2, 3, 5 og 7 (√97 ≈ 9,8). Hvis ingen af dem går op i tallet, er det et primtal. Uendeligt mange primtal: Euklid beviste omkring 300 f.Kr., at der findes uendeligt mange primtal. Det største kendte primtal (pr. 2024) har over 40 millioner cifre. Hvorfor primtal er vigtige: RSA-kryptering (som sikrer netbank, e-mail og HTTPS) bygger på, at det er let at gange to store primtal sammen, men i praksis umuligt at finde primfaktorerne ud fra resultatet.