Alkuluku
Alkuluku on lukua 1 suurempi luonnollinen luku, joka ei ole jaollinen muilla positiivisilla kokonaisluvuilla kuin yhdellä ja itsellään. Alkulukujen joukkoa merkitään kirjaimella P. Ensimmäiset alkuluvut ovat 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Alkulukuja on ääretön määrä. Lukua 1 suurempaa kokonaislukua, joka ei ole alkuluku, sanotaan yhdistetyksi luvuksi. Lukua 1 ei lueta alkuluvuksi, vaikka se onkin jaoton luku, jotta alkulukuja koskevien matemaattisten lauseiden muotoilu olisi yksinkertaisempaa. Alkulukujen laskemiseksi on olemassa useita algoritmeja. Yksi yksinkertaisimmista algoritmeista on Eratostheneen seula, joskin se on työläs ja hidas suurten alkulukujen etsimiseen.
Kaksi lukua ovat alkulukuja toistensa suhteen eli keskenään jaottomia, jos niillä ei ole ykköstä suurempia yhteisiä tekijöitä.
1600-luvulla elänyt ranskalainen matemaatikko Pierre de Fermat tarkasteli ensimmäisiä lukuja epänegatiivisten kokonaislukujen  n (0, 1, 2, 3, 4, ...) funktiossa
ja päätteli virheellisesti, että kaikki näin saadut luvut (3, 5, 17, 257, 65537, ...) olisivat alkulukuja.
Jokainen luonnollinen luku paitsi formula_2 voidaan jakaa alkulukutekijöihin eli kirjoittaa alkulukujen tulona. Voidaan osoittaa, että tämä tekijöihin jako on yksikäsitteinen lukuun ottamatta tekijöiden järjestystä (aritmetiikan peruslause). Voidaan esimerkiksi kirjoittaa
formula_3.
Tekijöihinjakoa, jossa alkulukutekijät ovat suuruusjärjestyksessä, kutsutaan kanoniseksi alkulukuhajotelmaksi.Eukleides antoi vanhimman tunnetun todistuksen alkulukujen määrän äärettömyydelle. Todistus on lyhyesti seuraava:
Alkuluvuille on olemassa laskufunktio formula_19. Merkintä formula_19 tarkoittaa lukua n pienempien alkulukujen määrää.
Alkulukujen tiheys on laskeva. 
Alkulukulause antaa asymptoottisen arvion formula_19-funktion käyttäytymiselle. Sen nojalla
Tämä merkintä ei tarkoita sitä, että näiden funktioiden arvojen erotus lähestyy nollaa, kun x lähestyy ääretöntä, vaan sitä, että niiden arvojen osamäärä lähestyy yhtä, kun x lähestyy ääretöntä. Arvion antama virhe voi siis olla suurikin, mutta suhteutettuna x:ään se on tarpeeksi pieni, jotta arvio on hyödyllinen.
Alkulukuteoreeman esitti ensimmäisen kerran Gauss konjektuurina 1800-luvulla. Sen todistivat toisistaan riippumatta Hadamard ja de la Vallée Poussin vuonna 1896.
Seuraava yhtälö tuottaa luonnollisen luvun formula_8 eri arvoilla kaikki alkuluvut ja vain ne: 
formula_24.
Tämän lausekkeen arvo on formula_25, jos tämä on alkuluku, muussa tapauksessa 2. Luvun formula_8 arvoilla 1 – 12 lauseke saa arvot 2, 3, 2, 5, 2, 7, 2, 2, 2, 11, 2 ja 13.
Kaavan hyöty on kuitenkin lähinnä teoreettinen, koska kertoman laskeminen on erittäin työlästä tietokoneillekin.
Esimerkiksi alkulukua formula_27 varten täytyy laskea luvun formula_28 kertoma, joka on formula_29.
Ohjelman pseudokoodi:
Suurin tunnettu alkuluku on formula_30. Tässä luvussa on 23 249 425 numeroa. Se on 50. tunnettu Mersennen alkuluku.
Toiseksi suurin tunnettu alkuluku on formula_31. Tässä luvussa on 22 338 618 numeroa. Se on 49. tunnettu Mersennen alkuluku. Alkuluvun löysi 7. tammikuuta 2016 GIMPS-projektissa mukana ollut tietokone.
Kolmanneksi suurin tunnettu alkuluku on formula_32. Tässä luvussa on noin 17 miljoonaa numeroa. Se on 48. tunnettu Mersennen alkuluku. Alkuluvun löysi 25. tammikuuta 2013 Central Missourin yliopiston professori Curtis Cooperin tietokone, joka osallistui GIMPS-projektiin.
Neljänneksi suurin tunnettu alkuluku on formula_33. Tässä luvussa on 12 978 189 numeroa. Se on 45. tunnettu Mersennen alkuluku. Alkuluvun löysi 23. elokuuta 2008 University of California, Los Angelesin matematiikan osaston tietokone, joka osallistui GIMPS-projektiin.
Viidenneksi suurin tunnettu alkuluku on formula_34. Tässä luvussa on 12 837 064 numeroa. Se on 47. tunnettu Mersennen alkuluku. Alkuluvun löysi 12. kesäkuuta 2009 Odd Magnar Strindmo, joka osallistui GIMPS-projektiin.
Kuudenneksi suurin tunnettu alkuluku on formula_35. Tässä luvussa on 11 185 272 numeroa. Se on 46. tunnettu Mersennen alkuluku. Alkuluvun löysi 6. syyskuuta 2008 Hans-Michael Elvenich Saksan Langenfeldistä, joka osallistui GIMPS-projektiin. Tämä oli ensimmäinen epäjärjestyksessä löytynyt Mersennen alkuluku sitten vuoden 1988.
Seitsemänneksi suurin tunnettu alkuluku on formula_36. Tässä luvussa on 9 808 358 numeroa. Se on 44. tunnettu Mersennen alkuluku. Alkuluvun löysi 4. syyskuuta 2006 University of Central Missourin ryhmä, joka osallistui GIMPS-projektiin.
Kahdeksanneksi suurin tunnettu alkuluku on formula_37 . Tässä luvussa on 9 152 052 numeroa. Se on 43. tunnettu Mersennen alkuluku, jonka löysivät professorit Curtis Cooper ja Steven Boone GIMPS-projektin avulla 15. joulukuuta 2005.
Suurin tunnettu alkuluku joka "ei ole" Mersennen alkuluku on formula_38. Siinä on 3 918 990 numeroa. Se löydettiin Seventeen or Bust -projektin avulla 26.3.2007.
Matematiikassa on monia alkulukuja koskevia avoimia kysymyksiä, joista varmastikin tunnetuin on Riemannin hypoteesi. Alla on lueteltu muita tunnettuja avoimia kysymyksiä.