Algarv

Algarv (ingl prime number) on naturaalarv, mis on suurem kui 1 ja mis jagub ainult arvuga 1 või iseendaga. Seega eristuvad algarvud naturaalarvude hulgas seetõttu, et neil on täpselt kaks erinevat naturaalarvulist jagajat. Naturaalarve, mis peale ühe ja iseendaga jagumise jaguvad veel vähemalt mingi kolmanda naturaalarvuga, nimetatakse kordarvudeks. Arv 1 ei ole algarv ega kordarv.

Algarvude hulk 
Algarve tähistatakse tavaliselt sümbolitega  ja , vajadusel kasutatakse indekseid. Kõigist algarvudest koosnevat naturaalarvude hulga alamhulka tähistatakse tavaliselt sümboliga  .

Vahetult on algarvude hulgaga  seotud kasvavalt järjestatud algarvude jada . Seega

,

kusjuures

 .

IV sajandil eKr järeldas Vana-Kreeka matemaatik Eukleides loogiliselt, et leidub lõpmata palju algarve. Tõestuse viis Eukleides läbi vastuväiteliselt, oletades, et algarve on lõplik hulk  ja konstrueerides seejärel naturaalarvu . Nii konstrueeritud naturaalarv ei saa olla algarv, sest ei leidu suuremaid algarve kui , seetõttu peab ta olema kordarv ja tal leidub algarvulisi jagajaid. Kui mingi algarv  jagab arvu  ja võrduse paremal poolel olevat algarvude korrutist, siis peab ta jagama ka arvu 1, mis ei ole aga võimalik, sest . Vastuolu tekkis oletusest, et algarve on lõplik hulk. Tänapäeval tuntakse seda väidet Eukleidese teoreemina, millel on terve rida tuntud tõestusi.

Algarvude jaotumine 
Algarvude asukoht naturaalarvude reas tundub olevat juhuslik. Kaks algarvu 2 ja 3 on järjestikused naturaalarvud. Leidub ka üksteisele väga lähedal asuvaid algarve. Algarve kujul  ja  nimetatakse algarvukaksikuteks. Näiteks 29 ja 31 või 41 ja 43 .

On tõestatud, et iga naturaalarvu  korral leidub arvude  ja  vahel algarv.

Sümboliga  tähistatakse naturaalarvu  mitteületavate algarvude arvu. Funktsiooni  nimetatakse algarvude jaotusfunktsiooniks. Väikeste argumentide korral saab funktsiooni  väärtusi leida peast:  . Suurte arvude jaoks on saadud ligikaudne hinnang:

.

Algarvude genereerimine 
Üks vanimaid algoritme algarvude tabeli koostamiseks on Vana-Kreeka matemaatiku Eratosthenese poolt III sajandil eKr loodud lihtne meetod, mida tuntakse Eratosthenese sõelana: kõik algarvud, välja arvatud arv 2, kuuluvad paaritute arvude hulka ja sisalduvad reas

Iga kordarv on mingi algarvu kordne, seega tuleb arvureas maha tõmmata kõik algarvu 3 kordsed alates arvust . Järgmine algarv on 5, nüüd saab maha tõmmata arvu 5 kordsed alates arvust . Analoogiliselt toimitakse edasi. Kui algarvust  väiksemate algarvude kordsed on maha tõmmatud, siis kõik allesjäänud arvud, mis on väiksemad kui , on algarvud. Nii saab leida kõik algarvud vahemikus , kus  on mingi etteantud naturaalarv.

Algarvude saamiseks on püütud leida ka valemeid. Näiteks Millsi valem

või Wrighti valem

,

kus  tähistab suurimat täisarvu, mis on väiksem kui . Seni leitud valemeid ei loeta lihtsateks ja efektiivseteks.

Viited

Välislingid

Citizendiumi artikkel

Arvuteooria
Elementaarmatemaatika