Alkulukutesti ja alkutekijöihin jako

Alkuluku on luonnollinen luku, joka on suurempi kuin 1 ja jolla ei ole muita positiivisia tekijöitä kuin 1 ja luku itse. Ensimmäiset alkuluvut ovat 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... 2 on ainoa parillinen alkuluku: Kaikki muut parilliset luvut ovat jaollisia kahdella, joten ne ovat yhdistettyjä lukuja. Tämä tekee luvusta 2 ainutlaatuisen alkulukujen joukossa. Näin tarkistat, onko luku alkuluku: Riittää, että testaat jaollisuuden alkuluvuilla neliöjuureen asti. Esimerkiksi luvun 97 kohdalla tarkistetaan luvut 2, 3, 5 ja 7 (√97 ≈ 9,8). Jos mikään niistä ei jaa lukua tasan, luku on alkuluku. Alkulukuja on äärettömän monta: Eukleides todisti noin 300 eaa., että alkulukuja on äärettömän monta. Suurimmassa tunnetussa alkuluvussa (vuoden 2024 tilanne) on yli 40 miljoonaa numeroa. Miksi alkuluvut ovat tärkeitä: RSA-salaus (joka suojaa verkkopankkia, sähköpostia ja HTTPS-yhteyksiä) perustuu siihen, että kahden suuren alkuluvun kertominen on helppoa, mutta tuloksen jakaminen takaisin alkutekijöihin on laskennallisesti käytännössä mahdotonta.