prime_numbers_count.tex

\subsection{Оценка числа простых чисел}
\selectlanguage{russian}

Функция $\pi(n)$ определяется как количество простых\index{число!простое} чисел из диапазона $[2, n]$.
Существует предел~\cite{Hadamard:1896}, ~\cite{de la Vallée-Poussin:1896}
    \[ \lim\limits_{n \rightarrow \infty}\frac{ \pi(n)}{ \frac{n}{\ln n}}=1. \]

Для $n \geq 17$ верно неравенство $\pi(n) > \frac{n}{\ln n}$.

Идея поиска(генерации) простых чисел состоит в случайном выборе числа и тестировании его на простоту.

Вероятность $P_k$ того, что случайное $k$-битовое число $n$ будет простым, равна
    \[ \lim\limits_{k \rightarrow \infty} P_k = \frac{1}{\ln n} = \frac{1}{k \ln 2}. \]

\example
    Вероятность того, что случайное 500-битное число, включая чётные числа, будет простым, примерно равна $\frac{1}{347}$, вероятность простоты случайного 2000-битного числа примерно равна $\frac{1}{1386}$.
\exampleend

Для дальнейшего рассмотрения интересен также вопрос об оценке вероятности того, что число $n$ будет простым, если оно априори взаимно простое с первыми $L$ простыми числами.

Пусть
    \[ \Delta_L = 2 \cdot 3 \cdot 5 \cdot ~\cdots~ \cdot p_L = \prod \limits_{p \leq p_L} p \] 
произведение первых $L$ простых чисел. Из теоремы о распределении простых чисел следует:
    \[ L \approx \frac{p_L}{\ln p_L}, ~~ p_L \approx L \ln L. \]
%TODO Что то из Чебышева

Вероятность того, что случайное \emph{нечётное} число не будет иметь общих делителей с первыми $L$ простыми числами, равна
    \[ P(L) = \prod \limits_{3 \leq p \leq p_L} \left( 1 - \frac{1}{p} \right). \]
Используя приближение $1-x \leq e^{-x}$, получаем:
   \[ P(L) ~\lesssim~ \operatorname{exp}\left(-\sum\limits_{3 \leq p \leq p_L} \frac{1}{p}\right) = \operatorname{exp}\left(\frac{1}{2}  - \sum\limits_{p \leq p_L} \frac{1}{p}\right). \]
Существует предел
    \[ \lim \limits_{n \rightarrow \infty} \left( \sum \limits_{p \leq n} \frac{1}{p} - \ln \ln n \right) = M, \]
называемый константой Мейсселя~---~Мертенса:\index{константа!Мейсселя~---~Мертенса}
    \[ M \approx 0.261497. \]
Упрощая уравнение, получаем:
    \[ P(L) \approx e^{\frac{1}{2} - \ln \ln p_L - M} = \frac{e^{\frac{1}{2} - M}}{\ln(L \ln L)}. \]