Prímszám-ellenőrzés és prímtényezős felbontás

A prímszám olyan 1-nél nagyobb természetes szám, amelynek az 1-en és önmagán kívül nincs más pozitív osztója. Az első prímszámok: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... A 2 az egyetlen páros prímszám: minden más páros szám osztható 2-vel, így összetett. Ezért a 2 különleges a prímszámok között. Hogyan ellenőrizhető, hogy egy szám prím-e: elég a négyzetgyökéig terjedő prímszámokkal való oszthatóságot vizsgálni. A 97 teszteléséhez próbálja ki a 2-t, 3-at, 5-öt és 7-et (√97 ≈ 9,8). Ha egyik sem osztja maradék nélkül, a szám prím. Végtelen sok prímszám van: Eukleidész Kr. e. 300 körül bebizonyította, hogy végtelen sok prímszám létezik. A legnagyobb ismert prímszám (2024-es állapot szerint) több mint 40 millió számjegyből áll. Miért fontosak a prímszámok: az RSA-titkosítás (az internetes bankolás, az e-mail és a HTTPS védelme) azon alapul, hogy két nagy prímszámot könnyű összeszorozni, a szorzatot viszont prímtényezőire bontani gyakorlatilag kivitelezhetetlen.