Primtallssjekk og primtallsfaktorisering

Et primtall er et naturlig tall større enn 1 som ikke har andre positive divisorer enn 1 og seg selv. De første primtallene er 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... 2 er det eneste partallige primtallet: Alle andre partall er delelige med 2 og dermed sammensatte. Det gjør 2 unikt blant primtallene. Slik sjekker du om et tall er et primtall: Du trenger bare å teste delelighet med primtall opp til kvadratroten. For å teste 97: sjekk 2, 3, 5 og 7 (√97 ≈ 9,8). Hvis ingen av dem går opp i tallet, er det et primtall. Uendelig mange primtall: Euklid beviste rundt 300 f.Kr. at det finnes uendelig mange primtall. Det største kjente primtallet (per 2024) har over 40 millioner sifre. Hvorfor primtall er viktige: RSA-kryptering (som sikrer nettbank, e-post og HTTPS) bygger på at det er enkelt å multiplisere to store primtall, men praktisk talt umulig å regne seg tilbake til primtallsfaktorene ut fra resultatet.