欧几里得数
首先我们来证明一下，素数有无穷多个。
假设素数只有 k 个，分别为 
，那么我们构造下面的数字：
显然 M 无法被 
中的任意一个整除，那么要么 M 可以被其他的素数整除，要么 M 自己就是一个素数。所以素数有无穷多个。
下面我们来定义欧几里得数，是用递归形式来定义的：
那么欧几里得数是否是素数呢？当然不是的， 
。
但是欧几里得数还是有很多奇妙的性质。
性质1
证明：
假设 
，那么有
性质2
如果令 
等于 
的最小素因子，那么 
就是一个不重复的素数序列，这也证明了素数有无穷多个。
性质3
在后面的章节可以证明：
其中 
下面我们稍稍探究一下下面这个数的性质：
这个数如果是素数，那么就被叫做梅森素数，那么它在什么情况下是素数呢？
首先 P 不能是合数，因为有
但是如果 P 是素数，这个数也不一定是素数，2017年年末美国一个电气工程师发现了人类历史上最大的梅森素数 
。
阶乘
阶乘定义如下：
所以有
由基本不等式可以得到
所以
所以
这里得到了阶乘的一个粗略范围，在后面章节中，我们会得到阶乘的一个更精确的表达式：
这就是斯特林数，搞ACM还是很有用的。
下面我们来探讨 
中含有多少个素因子 P ，个数记为 
。
从特殊情况讨论起，当 
的时候，我们首先看 
含有多少个2，然后看有多少个4，再看有多少个8，依次下去，所以答案为：
可以看出，这个答案不就是 N 的二进制表示不停右移1位，然后相加吗？所以又可以写成：
其中 
表示 n 的二进制表示中1的个数。
推广到一般情况：
如果我们令 
可以发现：
但是这个式子在什么情况下相等呢？这仍然是一个未解之谜。
所以 p 对 
的贡献度满足如下式子：
又因为 
，所以
假设素数只有 k 个，分别为 
，那么有
如果我们令 
，那么
这与我们之前推过的不等式矛盾！所以一定有无穷个素数。
设小于等于 n 的素数个数为 
，所以
根据斯特林数公式，我们可以得到
