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 . 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

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/\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<j}\left\lfloor {\frac {x}{p_{i}p_{j}}}\right\rfloor -\sum _{i<j<k}\left\lfloor {\frac {x}{p_{i}p_{j}p_{k}}}\right\rfloor +\cdots ,$

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.

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.

Portály: Matematika