素数永远不会穷尽
素数比任何给定的素数个数都多。
— 欧几里得，《几何原本》命题 IX.20 素数 是大于 1、只能被 1 和它自身整除的整数：2、3、5、7、11、13……其余的数，比如 $12=2\cdot2\cdot3$，都是素数的乘积。素数是算术的原子。
越往后，素数越稀少。1 到 100 之间有 25 个素数；1 000 001 到 1 000 100 之间只有 6 个。它们会不会在某处就没了？欧几里得用一个四行的论证证明了不会，英国数学家哈代认为它是整个数学中最美的论证之一。
证明 假设有人给你一份有限的素数清单 $p_1,p_2,\ldots,p_n$。欧几里得证明，至少有一个素数 不在 清单上。把它们全部相乘再加 1：
$$N=p_1\cdot p_2\cdots p_n+1.$$现在用清单上的任意一个素数去除 $N$。乘积 $p_1p_2\cdots p_n$ 能被它整除，所以 $N$ 除以它的余数是 1。清单上没有一个素数能整除 $N$。
但 $N$ 大于 1，所以它至少有一个素因子 $q$。为什么？取 $N$ 的大于 1 的最小因子。如果它不是素数，它就有一个更小的因子，而这个因子也整除 $N$，与"最小"矛盾。所以最小因子是素数。
这个素数 $q$ 整除 $N$，而清单上没有素数整除 $N$。所以 $q$ 不在清单上。任何有限的清单都不能包含所有素数：
$$\boxed{\text{素数有无穷多个。}}$$欧几里得没有说"无穷"，这个词希腊人是回避的。他说的是：给定 任何 个数的素数，总还有更多。这是同一件事，只是说得很谨慎。
构造出的数不一定是素数 一个常见的错误是以为 $N$ 总是素数。请看：
清单 $N$ $N$ 是素数吗？ 2 3 是 2, 3 7 是 2, 3, 5 31 是 2, 3, 5, 7 211 是 2, 3, 5, 7, 11 2 311 是 2, 3, 5, 7, 11, 13 30 031 不是：$30\,031=59\cdot509$ 在第六行，$N$ 是合数。但它的因子 59 和 509 都是不在清单上的素数。证明从来没有说 $N$ 是素数；它只说有 某个 新素数整除 $N$。至今仍不知道表中这种构造能否产生无穷多个素数。
