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] řeckého písmeneme π jako
π π -->
(
x
)
{\displaystyle \pi (x)}
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
/
ln
-->
(
x
)
{\displaystyle x/\operatorname {ln} (x)\!}
tedy že
lim
x
→ → -->
∞ ∞ -->
π π -->
(
x
)
x
/
ln
-->
(
x
)
=
1.
{\displaystyle \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 .
π π -->
(
x
)
{\displaystyle \pi (x)}
Pro malé hodnoty je nejsnazší explicitně zjistit všechna prvočísla menší než
x
{\displaystyle x}
Eratosthenova síta ) a sečíst je.
Legendre vymyslel propracovanější způsob výpočtu
π π -->
(
x
)
{\displaystyle \pi (x)}
x
{\displaystyle x}
p
1
{\displaystyle p_{1}}
p
2
{\displaystyle p_{2}}
p
k
{\displaystyle p_{k}}
p
i
{\displaystyle p_{i}}
x
{\displaystyle x}
⌊ ⌊ -->
x
⌋ ⌋ -->
− − -->
∑ ∑ -->
i
⌊
x
p
i
⌋
+
∑ ∑ -->
i
<
j
⌊
x
p
i
p
j
⌋
− − -->
∑ ∑ -->
i
<
j
<
k
⌊
x
p
i
p
j
p
k
⌋
+
⋯ ⋯ -->
,
{\displaystyle \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
{\displaystyle p_{1}}
p
2
{\displaystyle p_{2}}
p
k
{\displaystyle p_{k}}
x
{\displaystyle x}
π π -->
(
x
)
− − -->
π π -->
(
x
)
+
1
{\displaystyle \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
Reference
V tomto článku byl použit překlad textu z článku Prime-counting function
