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 (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.
náhled|vpravo|400px|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
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 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.
Odkazy
Související články Prvočíselná věta
Externí odkazy
Reference
Kategorie:Teorie čísel Kategorie:Prvočísla