最小的质数

2是最小的质数，也是唯一的一个既是偶数又是质数的数．也就是说，除了2以外，质数都是奇数。

小于100的质数有如下25个：2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97

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

大于1的自然数若不是素数，则称之为合数（也称为合成数）。例如，5是个素数，因为其正约数只有1与5。而6则是个合数，因为除了1与6外，2与3也是其正约数。算术基本定理确立了素数于数论里的核心地位：任何大于1的整数均可被表示成一串唯一素数之乘积。为了确保该定理的唯一性，1被定义为不是素数，因为在因式分解中可以有任意多个1（如3、1×3、1×1×3等都是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年以来，所有已知最大的素数都由电脑所发现。对更大素数的搜寻已在数学界以外的地方产生出兴趣。互联网梅森素数大搜索及其他用来寻找大素数的分散式运算计划变得流行，在数学家仍持续与素数理论奋斗的同时。