Prvočíselná funkce

matematická funkce udávající počet prvočísel

Prvočíselná funkce je funkce udávající počet prvočísel menších nebo rovných zadanému reálnému číslu x [1][2]. Bývá značena pomocí řeckého písmeneme π jako (ovšem nesouvisí nijak přímo se známějším Ludolfovým číslem) a je předmětem studia v matematice, v teorii čísel.

Hodnoty π(n) pro prvních 60 přirozených čísel

HistorieEditovat

Rozložení prvočísel mezi přirozenými čísly je předmětem zájmu číselných teoretiků již dlouho. Na konci 18. století vyslovili Carl Friedrich Gauss a Adrien-Marie Legendre domněnku, že prvočíselná funkce přibližně odpovídá funkci

 

tedy že

 

Tento výsledek, známý jako prvočíselná věta, se podařilo dokázat až v roce 1896, kdy jeho důkaz podali nezávisle na sobě Jacques Hadamard a Charles de la Vallée Poussin za použití Riemannovy funkce.

Algoritmy pro získání hodnoty Editovat

Pro malé hodnoty je nejsnazší explicitně zjistit všechna prvočísla menší než   (například pomocí Eratosthenova síta) a sečíst je.

Legendre vymyslel propracovanější způsob výpočtu  : Pro dané reálné číslo   a různá prvočísla   , …,   je počet přirozených čísel nesoudělných se všemi   a menších než   roven

 

Pokud za   , …,   zvolíme všechna prvočísla menší než odmocnina z  , je toto číslo rovno:

 

Ještě lepší algoritmy od té doby vymysleli například Ernst Meissel nebo Derrick Henry Lehmer.

OdkazyEditovat

Související článkyEditovat

Externí odkazyEditovat

ReferenceEditovat

V tomto článku byl použit překlad textu z článku Prime-counting function na anglické Wikipedii.

  1. BACH, Eric, Shallit, Jeffrey. Algorithmic Number Theory. [s.l.]: MIT Press, 1996. ISBN 0-262-02405-5. S. volume 1 page 234 section 8.8. 
  2. Prvočíselná funkce v encyklopedii MathWorld (anglicky)