Cesko.wiki Prvočíselná funkce
Author
Albert FloresPrvočíselná funkce je funkce udávající počet prvočísel menších nebo rovných zadanému reálnému číslu x . 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.
_pro_prvních_60_přirozené_číslo){kind=link}
Historie
Rozložení prvočísel mezi přirozenými čísly je předmětem zájmu číselných teoretiků již dlouho. Na konci +more_století'>18. století vyslovili Carl Friedrich Gauss a Adrien-Marie Legendre domněnku, ž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.\!
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 \pi(x)
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_1, p_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
Pokud za p_1, p_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.
