数学合集开篇我们认识了《》，本篇认识质数。

质数（Prime number，又称素数），指在大于 1 的自然数中，除了 1 和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。

例如：在数字 1 至 6 间，数字 2、3 与 5 为素数，1、4 与 6 则不是素数。

• 1 不是素数，其理由见下文，先放放稍后立马讲解。
• 2 是素数，因为只有 1 与 2 可整除该数。
• 3 是素数，因为 1 与 3 可整除 3，3 除以 2 会余 1。
• 4 是合数，因为 2 是另一个（除 1 与 4 外）可整除 4 的数：4 = 2 × 2。
• 5 是素数，数字 2、3 与 4 均不能整除 5。
• 6 是合数，会被 2 或 3 整除（同数字 4），因为 6 = 2 × 3。

在古埃及人的幸存纪录中，有迹象显示他们对素数已有部分认识：例如，在莱因德数学纸草书中的古埃及分数展开时，对素数与对合数有着完全不同的类型。不过，对素数有过具体研究的最早幸存纪录来自古希腊。公元前300年左右的《几何原本》包含与素数有关的重要定理，如有无限多个素数，以及算术基本定理。欧几里得亦展示如何从梅森素数建构出完全数。埃拉托斯特尼提出的埃拉托斯特尼筛法是用来计算素数的一个简单方法，虽然今天使用电脑发现的大素数无法使用这个方法找出。

希腊之后，到17世纪之前，素数的研究少有进展。1640年，皮埃尔·德·费马叙述了费马小定理（之后才被莱布尼茨与欧拉证明）。费马亦推测，所有具22n 1形式的数均为素数（称之为费马数），并验证至n = 4（即216 1）不过，后来由欧拉发现，下一个费马数232 1即为合数，且实际上其他已知的费马数都不是素数。法国修道士马兰·梅森发现有的素数具2p − 1的形式，其中p为素数。为纪念他的贡献，此类素数后来被称为梅森素数。

欧拉在数论中的成果，许多与素数有关。他证明无穷级数1/2 1/3 1/5 1/7 1/11 …会发散。1747年，欧拉证明每个完全数都确实为2p−1(2p − 1)的形式，其中第二个约数为梅森素数。

19世纪初，勒让德与高斯独立推测，当x趋向无限大时，小于x的素数数量会趋近于x/ln(x)，其中ln(x)为x的自然对数。黎曼于1859年有关ζ函数的论文中勾勒出一个程式，导出了素数定理的证明。其大纲由雅克·阿达马与查尔斯·贞·德·拉·瓦莱-普森所完成，他们于1896年独立证明出素数定理。

证明一个大数是否为素数通常无法由试除法来达成。许多数学家已研究过大数的素数测试，通常局限于特定的数字形式。其中包括费马数的贝潘测试（1877年）、普罗丝定理（约1878年）、卢卡斯-莱默素数判定法（1856年起）及广义卢卡斯素数测试。较近期的算法，如APRT-CL、ECPP及AKS等，均可作用于任意数字上，但仍慢上许多。

长期以来，素数被认为在纯数学以外的地方只有极少数的应用。到了1970年代，发明公共密钥加密这个概念之后，情况改变了，素数变成了RSA加密算法等一阶算法之基础。

自1951年以来，所有已知最大的素数都由电脑所发现。对更大素数的搜寻已在数学界以外的地方产生出兴趣。互联网梅森素数大搜索及其他用来寻找大素数的分散式运算计划变得流行，在数学家仍持续与素数理论奋斗的同时。

存在无限多个素数。另一种说法为，素数序列

2, 3, 5, 7, 11, 13, ...

永远不会结束。此一陈述被称为“欧几里得定理”，以古希腊数学家欧几里得为名，因为他提出了该陈述的第一个证明。已知存在其他更多的证明，包括欧拉的分析证明、哥德巴赫依据费马数的证明、佛丝登宝格使用一般拓扑学的证明，以及库默尔优雅的证明。

分析证明

欧几里得的证明取任一个由素数所组成的有限集合S。该证明的关键想法为考虑S内所有素数相乘后加一的一个数字：

。

如同其他自然数一般，N可被至少一个素数整除（即使N本身为素数亦同）。

任何可整除N的素数都不可能是有限集合S内的元素（素数），因为后者除N都会余1。所以，N可被其他素数所整除。因此，任一个由素数所组成的有限集合，都可以扩展为更大个由素数所组成之集合。

这个证明通常会被错误地描述为，欧几里得一开始假定一个包含所有素数的集合，并导致矛盾；或者是，该集合恰好包含n个最小的素数，而不任意个由素数所组成之集合。今日，n个最小素数相乘后加一的一个数字，被称为第n个欧几里得数。

解析证明

欧拉的证明使用到素数倒数的总和

。当p够大时，该和会大于任意实数。这可证明，存在无限多个素数，否则该和将只会增长至达到最大素数p为止。S(p)的增加率可使用梅滕斯第二定理来量化。比较总和