基于欧几里得的证明
定义2.1 定义函数 \(\pi(x)\) 为小于等于 \(x\) 的素数的个数，即
\[\pi(x)=\left|\{p|p\le x,p\in\mathbb{P}\}\right| \]
这个函数可以反映素数的分布信息。由欧几里得对素数无限的证明中我们知道
\[p_1p_2p_3\cdots p_n+1\ge p_{n+1} \]进一步，我们可以得到
\[p_n^n+1\ge p_{n+1} \]通过这个不等式，我们可以得到 \(\pi(x)\) 的一个估计
定理2.1
\[\pi(x)\ge\ln\ln{x} \]
证明：当 \(n=1\) 时，\(2^{2^n}=4>p_1=2\) .归纳地假设对于 \(n-1\) 时 \(2^{2^{n-1}}>p_{n-1}\) ，则
\[2^{2^1}\cdot2^{2^2}\cdot\cdots\cdot2^{2^{n-1}}+1= 2^{2^1+2^2+\cdots+2^{n-1}}+1= 2^{{2^n}-1}+1>p_n \]此时又有 \(2^{2^n}>2^{{2^n}-1}+1\) ，这样就完成了归纳。
而在 \(n\) 充分大的时候有 \(\text{e}^{\text{e}^{n}}>\text{e}^{\text{e}^{n-1}}>2^{2^n}\) . 则设 \(x\) 足够大，令
\[\text{e}^{\text{e}^{n}}>x>\text{e}^{\text{e}^{n-1}}>2^{2^n} \]那么有
\[\pi(x)= n>\ln\ln x \]对于前面有限项验证即可。 \(\Box\)
基于埃尔德什的证明
由埃尔德什证明素数无限的方法，我们可以得到一个更精确的估计。
证明 (素数无限) : 固定自然数 \(n\) ，则从 \(1\) 到 \(n\) 的每一个数都可以被唯一的表示成 \(n=rs^2\) 的形式，其中 \(r\) 不能再写成平方数的形式（\(1^2\) 例外）。则 \(s\) 可能的取值至多不会超过 \(\sqrt n\) ，而 \(r\) 的取值的可能性由算术基本定理知至多不会超过 \(2^k\) 种可能，其中 \(k=\pi(n)\) . 若素数有限，则当 \(n\) 足够大时，有 \(2^k\sqrt n\ge n\) 恒成立，其中 \(k\) 为定值。由幂函数的性质知这个不等式在 \(n>2^{2k}\) 时不成立，这样就导出了矛盾。 \(\Box\)
推论2.1
\[\pi(x)\ge \frac{\ln x}{2\ln 2} \]
标签：数论,text,ge,sqrt,ln,素数,初探,pi From： https://www.cnblogs.com/XingMath/p/16993332.html证明：由前面证明知对于小于 \(x\) 的素数的个数 \(k\) 有 \(2^{k}\sqrt n\ge n\) 于是得到
\[\begin{align}\nonumber2^{\pi(x)}&\ge\sqrt x\\ \nonumber\pi(x)&\ge\ln\sqrt x\\ \nonumber&=\frac{\ln x}{2\ln 2}\end{align} \]\(\Box\)