Algarv
Allikas: Vikipeedia
Algarvuks nimetatakse ühest suuremat naturaalarvu, mis jagub vaid arvuga 1 ja iseendaga. Algarvude hulk on lõpmatu, nagu tõestati juba antiikajal. Naturaalarvust n mitte suuremate algarvude arvu tähistatakse sümboliga π(n).
Sajast väiksemad algarvud (π(100) = 25) on 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 ja 97.
Kaksikuteks nimetatakse selliseid algarve, mille vahe on 2, näiteks 101 ja 103 või 1 000 000 007 ja 1 000 000 009. Ka kaksikute algarvude hulk on lõpmatu.
Kontrollimine, kas mingi konkreetne suur arv on algarv või ei, on väga keeruline: selle keerukus on O(
), kus n on arvu pikkus kahendsüsteemis. On tõestatud, et sellele probleemile head (ehk polünomiaalse keerukusega) algoritmi ei leidu. Sellel põhineb hulk krüpteerimisalgoritme.
[redigeeri] Vaata ka
- Kordarv
- Eukleidese teoreem
- Gaussi algarv
- Fermat' algarv
