素数

1是否为素数

最早期的希腊人甚至不将1视为是一个数字，因此不会认为1是素数。到了中世纪与文艺复兴时期，许多数学家将1纳入作为第一个素数。到18世纪中期，基督徒哥德巴赫在他与李昂哈德·欧拉著名的通信里将1列为第一个素数，但欧拉不同意。然而，到了19世纪，仍有许多数学家认为数字1是个素数。例如，德里克·诺曼·雷默（Derrick Norman Lehmer）在他那最大达10,006,721的素数列表中，将1列为第1个素数。昂利·勒贝格据说是最后一个称1为素数的职业数学家。到了20世纪初，数学家开始认为1不是个素数，但反而作为“单位”此一特殊类别。
许多数学成果在称1为素数时，仍将有效，但欧几里何的算术基本定理（如上所述）则无法不重新叙述而仍然成立。例如，数字15可分解成3 · 5及 1 · 3 · 5；若1被允许为一个素数，则这两个表示法将会被认为是将15分解至素数的不同方法，使得此一定理的陈述必须被修正。同样地，若将1视为素数，埃拉托斯特尼筛法将无法正常运作：若将1视为素数，此一筛法将会排除掉所有1的倍数（即所有其他的数），只留下数字1。此外，素数有几个1所没有的性质，如欧拉函数的对应值，以及除数函数的总和。

历史

在古埃及人的幸存纪录中，有迹象显示他们对素数已有部分认识：例如，在莱因德数学纸草书中的古埃及分数展开时，对素数与对合数有着完全不同的类型。不过，对素数有过具体研究的最早幸存纪录来自古希腊。公元前300年左右的《几何原本》包含与素数有关的重要定理，如有无限多个素数，以及算术基本定理。欧几里得亦展示如何从梅森素数建构出完全数。埃拉托斯特尼提出的埃拉托斯特尼筛法是用来计算素数的一个简单方法，虽然今天使用电脑发现的大素数无法使用这个方法找出。
希腊之后，到17世纪之前，素数的研究少有进展。1640年，皮埃尔·德·费马叙述了费马小定理（之后才被莱布尼茨与欧拉证明）。费马亦推测，所有具形式的数均为素数（称之为费马数），并验证至（即2¹⁶ + 1）不过，后来由欧拉发现，下一个费马数2³² + 1即为合数，且实际上其他已知的费马数都不是素数。法国修道士马兰·梅森发现有的素数具的形式，其中为素数。为纪念他的贡献，此类素数后来被称为梅森素数。
欧拉在数论中的成果，许多与素数有关。他证明无穷级数会发散。1747年，欧拉证明每个偶完全数都确实为的形式，其中第二个约数为梅森素数。
19世纪初，勒让德与高斯独立推测，当趋向无限大时，小于的素数数量会趋近于，其中为的自然对数。黎曼于1859年有关ζ函数的论文中勾勒出一个程式，导出了素数定理的证明。其大纲由雅克·阿达马与查尔斯·贞·德·拉·瓦莱-普森所完成，他们于1896年独立证明出素数定理。
证明一个大数是否为素数通常无法由试除法来达成。许多数学家已研究过大数的素性测试，通常局限于特定的数字形式。其中包括费马数的贝潘测试（1877年）、普罗丝定理（约1878年）、卢卡斯-莱默素数判定法（1856年起）及广义卢卡斯素性测试。较近期的算法，如APRT-CL、ECPP及AKS等，均可作用于任意数字上，但仍慢上许多。
长期以来，素数被认为在纯数学以外的地方只有极少数的应用。到了1970年代，发明公共密钥加密这个概念之后，情况改变了，素数变成了RSA加密算法等一阶算法之基础。
自1951年以来，所有已知最大的素数都由电脑所发现。对更大素数的搜寻已在数学界以外的地方产生出兴趣。互联网梅森素数大搜索及其他用来寻找大素数的分散式运算计划变得流行，在数学家仍持续与素数理论奋斗的同时。

测试素数与整数分解

确认一个数是否为素数有许多种方法。最基本的程序为试除法，但因为速率很慢，没有什么实际用处。有一类现代的素性测试可适用于任意数字之上，另有一类更有效率的测试方法，则只能适用于特定的数字之上。大多数此类方法只能辨别是否为素数。也能给出的一个（或全部）素因数之程序称之为约数分解算法。

试除法

测试是否为素数的最基本方法为试除法。此一程序将n除以每个大于1且小于等于的平方根之整数。若存在一个相除为整数的结果，则不是素数；反之则是个素数。实际上，若是个合数（其中与），则其中一个约数或必定至大为。例如，对使用试除法，将37除以，没有一个数能整除37，因此37为素数。此一程序若能知道直至的所有素数列表，因为试除法只检查为素数的状况，所以会更有效率。例如，为检查37是否为素数，只有3个相除是必要的（），因为4与6为合数。
作为一个简单的方法，试除法在测试大整数时很快地会变得不切实际，因为可能的约数数量会随着n的增加而迅速增加。依据下文所述之素数定理，小于的素数之数量约为，因此使用试除法测试是否为素数时，大约会需要用到这么多的数字。对，此一数值约为4.5亿，对许多实际应用而言都太过庞大。

筛法

一个能给出某个数值以下的所有素数之算法，称之为素数筛法，可用于只使用素数的试除法内。最古老的一个例子为埃拉托斯特尼筛法（见上文），至今仍最常被使用。阿特金筛法为另外一例。在电脑出现之前，筛法曾被用来给出10⁷以下的素数列表。

整数分解

给定一合数n，给出一个（或全部）素因数的工作称之为n的约数分解。椭圆曲线分解是一个依靠椭圆曲线上的运算来分解素因数的算法。

其他猜想

除了黎曼猜想之外，还有许多其他的猜想存在。虽然这些猜想的陈述大多很简单，但许多猜想经过了数十年仍提不出证明，如4个兰道问题，从1912年提出至今仍然未解。其中一个为哥德巴赫猜想，该猜想认为每个大于2的偶数n都可表示成两个素数之和。至于2011年2月，这个猜想对最大达n = 2 · 10¹⁷的所有数字都会成立。较弱形式的哥德巴赫猜想已被证明，如维诺格拉多夫定理，该定理表示每个足够大的奇数都可表示成三个素数之和。陈氏定理表示，每个足够大的偶数都可表示成一个素数与一个半素数（两个素数的乘积）之和。此外，任一个偶数均可写成六个素数之和。数论研究这些问题的分支称之为加法数论。反哥德巴赫猜想，所有的正偶数n都可以表示成两个素数之差，但此猜想可由波利尼亚克猜想类推证明。
其他猜想处理是否有无限多个具某些限制的素数这类问题。据猜想，存在无限多个斐波那契素数与无限多个梅森素数，但没有无限多个费马素数。还不知道是否存在无限多个维费里希素数与欧几里得素数。
第三种类型的猜想涉及到素数的分布情形。据猜想，存在无限多对孪生素数，即有无限多对相差2的素数（孪生素数猜想）。波利尼亚克猜想是比孪生素数猜想更强的一个猜想，该猜想表示存在无限多对相差2n的连续素数。据猜想，存在无限多个具n² + 1形式的素数。上述猜想都是申策尔猜想的特例。布罗卡猜想表示，在两个大于2的连续素数之平方数之间，总是会有至少4个素数。勒让德猜想表示，对每个正整数n，n²与(n + 1)²间总会存在一个素数。克拉梅尔猜想可导出勒让德猜想。

应用

长期以来，数论，尤其是对素数的研究，一般都会被认为是典型的纯数学，除了求知的趣味之外，没有其他应用。特别是，一些数论学家，如英国数学家戈弗雷·哈罗德·哈代即对其工作绝对不会有任何在军事上的重大性感到自豪。然而，此一观点在1970年代时遭到粉碎，当素数被公开宣布可以作为产生公钥加密算法的基础之时。素数现在也被用在杂凑表与伪乱数产生器里。
旋转机被设计成在每个转片上有不同数目的销，在每个转片上的销的数量都会是素数，亦或是会与其他转片上的销的数量互素。这有助于在重复所有的组合之前，让所有转片的可能组合都能出现过一次。
国际标准书号的最后一码为校验码，其算法使用到了11是个素数的这个事实。
在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数最好设计成素数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。
在害虫的生物生长周期与杀虫剂使用之间的关系上，杀虫剂的素数次数的使用也得到了证明。实验表明，素数次数地使用杀虫剂是最合理的：都是使用在害虫繁殖的高潮期，而且害虫很难产生抗药性。

以素数形式无规律变化的导弹和鱼雷可以使敌人不易拦截。

其他数学里出现的素数

许多数学领域里会大量使用到素数。举有限群的理论为例，西罗定理即是一例。该定理表示，若G是个有限群，且pⁿ为素数p可整除G的阶的最大幂次，则G会有个pⁿ阶的子群。此外，任意素数阶的群均为循环群（拉格朗日定理）。

公开金钥加密

几个公开金钥加密算法，如RSA与迪菲－赫尔曼金钥交换，都是以大素数为其基础（如512位元的素数常被用于RSA里，而1024位元的素数则一般被迪菲-赫尔曼金钥交换所采用）。RSA依靠计算出两个（大）素数的相乘会比找出相乘后的数的两个素因数容易出许多这个假设。迪菲－赫尔曼金钥交换依靠存在模幂次的有效算法，但相反运算的离散对数仍被认为是个困难的问题此一事实。

自然里的素数

周期蝉属里的蝉在其演化策略上使用到素数。蝉会在地底下以幼虫的形态度过其一生中的大部分时间。周期蝉只会在7年、13年或17年后化蛹，然后从洞穴里出现、飞行、交配、产卵，并在至多数周后死亡。此一演化策略的原因据信是因为若出现的周期为素数年，掠食者就很难演化成以周期蝉为主食的动物。若周期蝉出现的周期为非素数年，如12年，则每2年、3年、4年、6年或12年出现一次的掠食者就一定遇得到周期蝉。经过200年以后，假设14年与15年出现一次的周期蝉，其掠食者的平均数量，会比13年与17年出现一次的周期蝉，高出2%。虽然相差不大，此一优势似乎已足够驱动天择，选择具素数年生命周期的这些昆虫。
据猜测，ζ函数的根与复数量子系统的能阶有关。

推广

素数的概念是如此的重要，以致此一概念被以不同方式推广至数学的不同领域里去。通常，“质”（prime）可在适当的意义下，用来表示具有最小性或不可分解性。例如，质体是指一个包含0与1的体F的最小子域。质体必为有理数或具有p个元素的有限域，这也是其名称的缘由。若任一对象基本上均可唯一地分解成较小的部分，则这些较小的部分也会用“质”这个字来形容。例如，在纽结理论里，质纽结是指不可分解的纽结，亦即该纽结不可写成两个非平凡纽结的连通和。任一纽结均可唯一地表示为质纽约的连通和。质模型与三维质流形亦为此类型的例子。

在艺术与文学里

素数也影响了许多的艺术家与作家。法国作曲家奥立佛·梅湘使用素数创造出无节拍音乐。在《La Nativite du Seigneur》与《Quatre etudes de rythme》等作品里，梅湘同时采用由不同素数给定之长度的基调，创造出不可预测的节奏：第三个练习曲《Neumes rythmiques》中出现了素数41、43、47及53。据梅湘所述，此类作曲方式是“由自然的运动，自由且不均匀的持续运动中获得的灵感”。
NASA科学家卡尔·萨根在他的科幻小说《接触未来》（Contact）里，认为素数可作为与外星人沟通的一种方式。这种想法是他与美国天文学家法兰克·德雷克于1975年闲聊时形成的。
许多电影，如《异次元杀阵》（Cube）、《神鬼尖兵》（Sneakers）、《越爱越美丽》（The Mirror Has Two Faces）及《美丽境界》（A Beautiful Mind），均反映出大众对素数与密码学之神秘的迷恋。保罗·裘唐诺所著的小说《素数的孤独》（The Solitude of Prime Numbers）里，素数被用来比喻寂寞与孤独，被描述成整数之间的“局外人”。
荒木飞吕彦所创作的日本漫画《JoJo的奇妙冒险》第六部《石之海》的反派普奇神父喜欢数素数，他认为素数是孤独的数字，并透过数素数安抚他紧张的情绪。