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 $p$ ja $q$, vajadusel kasutatakse indekseid. Kõigist algarvudest koosnevat naturaalarvude hulga alamhulka tähistatakse tavaliselt sümboliga $\mathbb {P}$.

Vahetult on algarvude hulgaga $\mathbb {P}$ seotud kasvavalt järjestatud algarvude jada $\left(p_{n}\right)_{n\in \mathbb {N} }$. Seega

$\mathbb {N} \varsupsetneq \mathbb {P} =\{p_{n}\mid n\in \mathbb {N} \}$,

kusjuures

$\left(p_{n}\right)_{n\in \mathbb {N} }=\left(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,\dotsc \right)$ (jada A000040 OEIS'es).

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 $p_{1},...,p_{n}$ ja konstrueerides seejärel naturaalarvu $a=p_{1}p_{2}...p_{n}+1$. Nii konstrueeritud naturaalarv ei saa olla algarv, sest ei leidu suuremaid algarve kui $p_{n}$, seetõttu peab ta olema kordarv ja tal leidub algarvulisi jagajaid. Kui mingi algarv $p_{i}$ jagab arvu $a$ ja võrduse paremal poolel olevat algarvude korrutist, siis peab ta jagama ka arvu 1, mis ei ole aga võimalik, sest $p_{i}>1$. 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 $p$ ja $p+2$ nimetatakse algarvukaksikuteks. Näiteks 29 ja 31 või 41 ja 43 (jada A001097 OEIS'es).

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

Sümboliga $\pi \left(n\right)$ tähistatakse naturaalarvu $n$ mitteületavate algarvude arvu. Funktsiooni $\pi \left(n\right)$ nimetatakse algarvude jaotusfunktsiooniks. Väikeste argumentide korral saab funktsiooni $\pi \left(n\right)$ väärtusi leida peast: $\pi \left(1\right)=0,\pi \left(2\right)=1,\pi \left(3\right)=2,...,\pi \left(10\right)=4,...$. Suurte arvude jaoks on saadud ligikaudne hinnang:

$\lim _{x\to \infty }{\frac {\pi (x)}{\frac {x}{\ln(x)}}}=1$.

Algarvude genereerimine

Eratosthenese sõel leiab naturaalarvude hulgast kõigepealt paarisarvud (punane), seejärel arvu 3 kordsed (roheline), arvu 5 kordsed (sinine) ja arvu 7 kordsed (kollane). Hallidele ruutudele jäänud arvud on väiksemad kui 11²=121 ja on seega algarvud.

Ü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

$3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,\ldots$

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

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

$\left\lfloor {A^{3^{n}}}\right\rfloor$

või Wrighti valem

$\left\lfloor 2^{2^{2^{\cdot ^{\cdot ^{\cdot ^{2^{\alpha }}}}}}}\right\rfloor$,

kus $\left\lfloor x\right\rfloor$ tähistab suurimat täisarvu, mis on väiksem kui $x$. Seni leitud valemeid ei loeta lihtsateks ja efektiivseteks.

Välislingid

• Citizendiumi artikkel