Prvočíselná funkce

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Prvočíselná funkce je funkce udávající počet prvočísel menších než zadané reálné číslo x [1][2]. Bývá značena pomocí řeckého písmeneme π jako \pi(x) (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

Historie[editovat | editovat zdroj]

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 předpoklad, že prvočíselná funkce přibližně odpovídá funkci

 x/\operatorname{ln}(x)\!

tedy že

\lim_{x\rightarrow\infty}\frac{\pi(x)}{x/\operatorname{ln}(x)}=1.\!

To se povedlo dokázat poprvé v roce 1896, kdy nezávisle dosáhli důkazu Jacques Hadamard a Charles de la Vallée Poussin za použití Riemannovy funkce.

Algoritmy pro získání hodnoty \pi(x)[editovat | editovat zdroj]

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

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

\lfloor x\rfloor - \sum_{i}\left\lfloor\frac{x}{p_i}\right\rfloor + \sum_{i<j}\left\lfloor\frac{x}{p_ip_j}\right\rfloor - \sum_{i<j<k}\left\lfloor\frac{x}{p_ip_jp_k}\right\rfloor + \cdots,

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

\pi(x)-\pi\left(\sqrt{x}\right)+1\,

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

Odkazy[editovat | editovat zdroj]

Související články[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

  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)

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