欧几里得数

首先我们来证明一下，素数有无穷多个。

假设素数只有$k$个，分别为$2,3, \ldots ,{P_k}$，那么我们构造下面的数字：
<!–swig2–>
显然$M$无法被$2,3, \ldots ,{P_k}$中的任意一个整除，那么要么$M$可以被其他的素数整除，要么$M$自己就是一个素数。所以素数有无穷多个。

下面我们来定义欧几里得数，是用递归形式来定义的：
<!–swig7–>

那么欧几里得数是否是素数呢？当然不是的，${e_5} = 1807 = 13 \cdot 139$。

但是欧几里得数还是有很多奇妙的性质。

性质1
<!–swig9–>
证明：
假设$n > m$，那么有
<!–swig11–>
性质2
如果令$q_j$等于$e_j$的最小素因子，那么${q_1},{q_2}, \ldots $就是一个不重复的素数序列，这也证明了素数有无穷多个。
性质3
<!–swig15–>
在后面的章节可以证明：
<!–swig16–>
其中$E \approx 1.264$

下面我们稍稍探究一下下面这个数的性质：
<!–swig18–>
这个数如果是素数，那么就被叫做梅森素数，那么它在什么情况下是素数呢？

首先$p$不能是合数，因为有
<!–swig20–>
但是如果$p$是素数，这个数也不一定是素数，2017年年末美国一个电气工程师发现了人类历史上最大的梅森素数——${2^{77232917}} - 1$。

阶乘

阶乘定义如下：
<!–swig23–>
所以有
<!–swig24–>
由基本不等式可以得到
<!–swig25–>
所以
<!–swig26–>
所以
<!–swig27–>
这里得到了阶乘的一个粗略范围，在后面章节中，我们会得到阶乘的一个更精确的表达式：
<!–swig28–>
这就是斯特林数，搞ACM还是很有用的。

下面我们来探讨$n!$中含有多少个素因子$p$，个数记为${\varepsilon _p}(n!)$。

从特殊情况讨论起，当$p = 2$的时候，我们首先看$n!$含有多少个2，然后看有多少个4，再看有多少个8，依次下去，所以答案为：
<!–swig34–>
可以看出，这个答案不就是$n$的二进制表示不停右移1位，然后相加吗？所以又可以写成：
<!–swig36–>
其中${\nu _2}(n)$表示$n$的二进制表示中1的个数。

推广到一般情况：
<!–swig39–>
放缩一下有：
<!–swig40–>

如果我们令$p = 2$和$p = 3$可以发现：
<!–swig43–>
但是这个式子在什么情况下相等呢？这仍然是一个未解之谜。

所以$p$对$n!$的贡献度满足如下式子：
<!–swig46–>
又因为$p \le 2^{p - 1}$，所以
<!–swig48–>
假设素数只有$k$个，分别为$2,3, \ldots ,{P_k}$，那么有
<!–swig51–>
如果我们令$n = {2^{2k}}$，那么
<!–swig53–>
这与我们之前推过的不等式矛盾！所以一定有无穷个素数。

设小于等于$n$的素数个数为$\pi (n)$，所以
<!–swig56–>
根据斯特林数公式，我们可以得到
<!–swig57–>