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. Pienimmät kymmenen alkulukua 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ä.

Luonnolliset luvut tulona

Jokainen luonnollinen luku paitsi  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
Tekijöihinjakoa, jossa alkulukutekijät ovat suuruusjärjestyksessä, kutsutaan kanoniseksi alkulukuhajotelmaksi.

Alkulukukaavoja

Seuraava funktio tuottaa luonnollisen luvun  eri arvoilla kaikki alkuluvut ja vain ne: 
Tämän lausekkeen arvo on , jos tämä on alkuluku, muussa tapauksessa 2.  Luvun  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  varten täytyy laskea luvun  kertoma, joka on .
Ohjelman pseudokoodi:
define factorial(n):
  if n == 0 or n == 1:
      return 1
  else:
      return n*factorial(n-1)

k = read_integer()
 
for n in 1 to k:
  c = factorial(n)
  prime = 2 + (2*c mod (n + 1))

  if prime not in seen_primes:
      seen_primes.insert(prime)
      print prime

Suurimpia tunnettuja alkulukuja

Suurin tunnettu alkuluku on . Tässä luvussa on 24 862 048 numeroa. Se on 51. tunnettu Mersennen alkuluku.
Toiseksi suurin tunnettu alkuluku on . Tässä luvussa on 23 249 425 numeroa. Se on 50. tunnettu Mersennen alkuluku.
Kolmanneksi suurin tunnettu alkuluku on . 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.
Neljänneksi suurin tunnettu alkuluku on . 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.
Viidenneksi suurin tunnettu alkuluku on . 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.
Kuudenneksi suurin tunnettu alkuluku on .  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.
Seitsemänneksi suurin tunnettu alkuluku on . 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.
Suurin tunnettu alkuluku joka ei ole Mersennen alkuluku on . Siinä on 3 918 990 numeroa. Se löydettiin Seventeen or Bust -projektin avulla 26.3.2007.