Prvočíselná funkce

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 $\mathrm{\pi <!--\; \pi \; -->}\left(x\right)$ (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.

Historie

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

$x/\ln <!--\; \; -->\left(x\right)$

tedy že

$\underset{x\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim}\frac{\mathrm{\pi <!--\; \pi \; -->}\left(x\right)}{x/\ln <!--\; \; -->\left(x\right)}=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 $\mathrm{\pi <!--\; \pi \; -->}\left(x\right)$

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 $\mathrm{\pi <!--\; \pi \; -->}\left(x\right)$: 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

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

$\mathrm{\pi <!--\; \pi \; -->}\left(x\right)-<!--\; -\; -->\mathrm{\pi <!--\; \pi \; -->}\left(\sqrt{x}\right)+1$

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

Odkazy

Související články

• Prvočíselná věta

Externí odkazy

• Obrázky, zvuky či videa k tématu prvočíselná funkce na Wikimedia Commons

Reference

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

Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.