Alkuluku on 1:tä suurempi kokonaisluku, jolla on täsmälleen kaksi tekijää: 1 ja itse. Alkuluvut ovat kaikkien kokonaislukujen rakennuspalikoita – jokainen kokonaisluku voidaan ilmaista alkulukujen tulona.

Ensimmäiset 25 alkulukua

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Huomaa, että 2 on ainoa parillinen alkuluku. Kaikki muut parilliset luvut ovat jaollisia kahdella.

Tapa 1: Kokeilujako

Yksinkertaisin tapa testata, onko luku alkuluku – tarkista, jakaako jokin luku sen neliöjuureen asti sen tasaisesti.

Avaintieto: Jos n:n kerroin on suurempi kuin √n, sillä on myös vastaava kerroin pienempi kuin √n. Joten sinun tarvitsee vain tarkistaa √n asti.

Algoritmi:

  1. Jos n < 2, ei alkuluku
  2. Jos n = 2, alkuluku
  3. Jos n on parillinen (paitsi 2), ei alkuluku
  4. Tarkista kaikki parittomat luvut väliltä 3 - √n
  5. Jos jokin jakaa n tasaisesti, ei alkulukua
  6. Muussa tapauksessa esikäsittely

Esimerkki: Onko 97 alkuluku?

√97 ≈ 9,85, joten tarkista alkuluvut aina 9:2, 3, 5, 7 asti

  • 97 ÷ 2 = 48,5 (ei koko)
  • 97 ÷ 3 = 32,33... (ei kokonainen)
  • 97 ÷ 5 = 19,4 (ei kokonainen)
  • 97 ÷ 7 = 13,86 (ei kokonainen)

Jakajia ei löytynyt — 97 on alkuluku.

Esimerkki: Onko 91 alkuluku?

√91 ≈ 9,54, tarkista enintään 9: 2, 3, 5, 7

  • 91 ÷ 7 = 13 (koko luku!)

91 ei ole alkuluku — 91 = 7 × 13.

Menetelmä 2: Eratosthenes-seula

Eratosthenesin seula löytää kaikki alkuluvut tiettyyn rajaan asti. Se on nopea ja tyylikäs, ja sen keksi kreikkalainen matemaatikko Eratosthenes noin vuonna 240 eaa.

Kaikki alkuluvut 50 asti:

  1. Kirjoita numerot 2-50
  2. Aloita numerolla 2 (ensimmäinen alkuluku). Yliviivaa kaikki luvun 2 kerrannaiset (4, 6, 8...)
  3. Siirry seuraavaan yliviivaamattomaan numeroon: 3. Yliviivaa 3:n kerrannaiset (9, 15, 21...)
  4. Seuraava yliviivaamaton: 5. Yliviivaa 5:n kerrannaiset (25, 35...)
  5. Seuraava yliviivaamaton: 7. Yliviivaa 7:n kerrannaiset (49...)
  6. Pysäytä, kun saavutat √50 ≈ 7.07
  7. Kaikki jäljellä olevat ylittämättömät luvut ovat alkulukuja

** Pohjustaa jopa 50:** 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Esittelee jopa 100: Täydellinen luettelo

Alue Primes
1–10 2, 3, 5, 7
11-20 11, 13, 17, 19
21–30 23, 29
31–40 31, 37
41–50 41, 43, 47
51–60 53, 59
61–70 61, 67
71–80 71, 73, 79
81–90 83, 89
91-100 97

Alle 100:ssa on 25 alkulukua.

Pikajakotestit

Ennen kuin teet täyden jaon, tarkista nämä säännöt:

Jaettavissa Jos...
2 Viimeinen numero on parillinen (0,2,4,6,8)
3 3:lla jaollinen numeroiden summa
5 Viimeinen numero on 0 tai 5
7 Ei yksinkertaista sääntöä - vain jaa
11 Vuorotteleva numerosumma, joka on jaollinen 11:llä

Esimerkki: Onko 143 alkuluku?

  • Ei edes ✓
  • 1+4+3 = 8, ei jaollinen 3:lla ✓
  • Ei pääty numeroihin 0 tai 5 ✓
  • √143 ≈ 11,96, tarkista 11 asti
  • 143 ÷ 7 = 20,43 ✓
  • 143 ÷ 11 = 13 - jaollinen!

143 = 11 × 13. Ei alkuluku.

Miksi Primes Matter

Salaus: RSA-salaus – jota käytetään verkkopankkitoiminnan, HTTPS:n ja sähköpostin suojaamiseen – perustuu siihen, että kahden suuren alkuluvun kertominen on helppoa, mutta tuloksen laskeminen alkulukuihin on erittäin vaikeaa.

Tietotekniikka: Hash-taulukot, satunnaislukugeneraattorit ja tarkistussummat käyttävät alkulukujen ominaisuuksia.

Puhdas matematiikka: Alkulukujakauma on edelleen yksi matematiikan syvimmistä ratkaisemattomista ongelmista — Riemannin hypoteesi.

Mielenkiintoisia ensisijaisia ​​faktoja

  • Suurimmassa tunnetussa alkuluvussa (vuodesta 2024) on yli 41 miljoonaa numeroa
  • Kaksoisalkuluvut ovat alkulukuja, jotka eroavat kahdella (11 ja 13, 17 ja 19, 41 ja 43)
  • Alkulukuja on äärettömän monta – Eukleides todisti noin 300 eaa
  • Goldbachin olettamus (todistettu vuodesta 1742): jokainen parillinen luku > 2 on kahden alkuluvun summa

Lue seuraavaksi