Algarv

Algarv(inglprime number) onnaturaalarv,mis on suurem kui 1 ja mis jagub ainult arvuga 1 või iseendaga. Seega eristuvad algarvudnaturaalarvude hulgasseetõttu, et neil on täpselt kaks erinevat naturaalarvulistjagajat.Naturaalarve, mis peale ühe ja iseendaga jagumise jaguvad veel vähemalt mingi kolmanda naturaalarvuga, nimetataksekordarvudeks.Arv 1 ei ole algarv ega kordarv.

Algarvude hulk

Algarve tähistatakse tavaliseltsümbolitega$p$ja$q$,vajadusel kasutatakseindekseid.Kõigist algarvudest koosnevat naturaalarvude hulgaalamhulkatähistatakse tavaliselt sümboliga$\mathbb {P}$.

Vahetult on algarvude hulgaga$\mathbb {P}$seotud kasvavalt järjestatud algarvudejada$\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)$(jadaA000040OEIS'es).

IV sajandil eKr järeldasVana-KreekamatemaatikEukleidesloogiliselt, et leidub lõpmata palju algarve.Tõestuseviis 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äidetEukleidese 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$nimetataksealgarvukaksikuteks.Näiteks 29 ja 31 või 41 ja 43 (jadaA001097OEIS'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)$nimetataksealgarvude 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õelleiab 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 vanimaidalgoritmealgarvude tabeli koostamiseks on Vana-Kreeka matemaatikuEratosthenesepoolt III sajandil eKr loodud lihtne meetod, mida tuntakseEratosthenese 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