素数

素数（或素整数，通常简称为“素数”）是一个正整数 ，除了 1 和 本身之外，没有其他正整数除数。更简洁地说，素数 是一个正整数，除了 1 之外，正好有一个正除数，这意味着它是一个不能被分解的数。例如，13 的唯一除数是 1 和 13，因此 13 是素数，而数字 24 的除数是 1、2、3、4、6、8、12 和 24（对应于因式分解 ），因此 24 不是素数。除 1 以外的正整数，如果不是素数，则称为合数。

虽然术语“素数”通常指正素整数，但也定义了其他类型的素数，例如高斯素数。

数字 1 是一个特例，它既不被认为是素数，也不被认为是合数 (Wells 1986, p. 31)。虽然数字 1 曾经被认为是素数 (Goldbach 1742; Lehmer 1909, 1914; Hardy and Wright 1979, p. 11; Gardner 1984, pp. 86-87; Sloane and Plouffe 1995, p. 33; Hardy 1999, p. 46)，但在许多涉及大于或等于 2 的素数的定义和应用中，它都需要特殊处理，因此通常将其归为一类。不称 1 为素数的一个很好的理由是，如果 1 是素数，那么算术基本定理的陈述就必须修改，因为“以正好一种方式”将是错误的，因为任何 。换句话说，如果素数包含 1，则唯一分解为素数的乘积将失败。Tietze (1965, p. 2) 指出了一个稍微不那么启发性但数学上正确的原因，他指出“为什么数字 1 被排除在外？这是一个小学生经常争论的问题，但由于这是一个定义问题，因此无可争辩。”正如 Derbyshire (2004, p. 33) 更简单地指出，“2 [作为素数] 在平衡方面是值得的；1 则不然。”

排除 1 后，最小的素数是 2。然而，由于 2 是唯一的偶素数（具有讽刺意味的是，在某种意义上，它也是“最奇怪”的素数），它也有些特殊，因此排除 2 的所有素数的集合被称为“奇素数”。另请注意，虽然 2 今天被认为是素数，但曾经有一段时间它不是 (Tietze 1965, p. 18; Tropfke 1921, p. 96)。

第 个素数通常表示为 ，因此 、 等等，并且可以在 Wolfram 语言 中计算为Prime[n]。

前几个素数是 2、3、5、7、11、13、17、19、23、29、31、37、... (OEIS A000040; Hardy and Wright 1979, p. 3)。记住前七个素数的助记符是，“在清晨，天文学家使非数学家精神化”（G. L. Honaker, Jr.，私人通信，2005 年 8 月 4 日）。在小说深夜小狗神秘习题 (Haddon 2003) 中，主角克里斯托弗有趣地使用素数而不是（更）传统的正整数来为章节编号。在电视剧数字追凶第一季剧集“头号嫌疑犯” (2005) 中，数学天才查理·埃普斯意识到角色伊森的女儿被绑架是因为他即将解决黎曼猜想，据称这将使犯罪者能够通过分解大数来破解基本上所有的互联网安全。

中十进制数字的位数，对于 、1、... 由 1、2、3、4、6、7、8、9、10、11、12、13、14、... 给出 (OEIS A099260)。

素数的集合有时表示为 ，在 Wolfram 语言 中表示为Primes.

上面以二进制位的序列说明了前几个素数。

欧拉评论道：“数学家们至今徒劳地试图发现素数序列中的某种规律，我们有理由相信这是一个思想永远无法穿透的谜团”（Havil 2003, p. 163）。在 1975 年的一次演讲中，D. Zagier 评论道：“关于素数的分布，我有两个事实希望能够让你确信，它们将永远铭刻在你的心中。第一个事实是，尽管它们的定义很简单，并且作为自然数的构建块，素数像杂草一样在自然数中生长，似乎除了机会法则之外没有其他法则，没有人可以预测下一个素数会在哪里出现。第二个事实甚至更令人惊讶，因为它恰恰相反：素数表现出惊人的规律性，存在支配其行为的规律，并且它们几乎以军事般的精确度遵守这些规律”（Havil 2003, p. 171）。

第 个素数，对于 、1、... 由 2、29、541、7919、104729、1299709、15485863、179424673、2038074743、... 给出 (OEIS A006988; Graham et al. 1990, p. 111)。

大素数 (Caldwell) 包括大的梅森素数、费雷尔素数和 位数字的反例 ，表明 5359 不是第二类谢尔宾斯基数 (Helm 和 Norris)。截至 2024 年 10 月，已知最大的素数是梅森素数 ，它有惊人的 位十进制数字。

素数可以通过筛选过程（例如埃拉托斯特尼筛法）生成，而幸运数也是通过筛选生成的，并且似乎与素数共享一些有趣的渐近性质。素数满足许多奇怪而美妙的性质。虽然存在显式的素数公式（即，要么为所有值生成素数，要么将第 个素数作为 的函数），但它们是人为设计的，以至于几乎没有实际价值。

素数特征函数的狄利克雷生成函数 由下式给出

			(1)
			(2)
			(3)

其中 是素数 zeta 函数， 是一个艾弗森括号。

给出小于或等于数字 的素数个数的函数表示为 ，称为素数计数函数。给出 渐近形式的定理称为素数定理。类似地，小于或等于数字 的 形式的素数个数表示为 ，称为模素数计数函数。

和 是反函数，因此

(4)

对于所有正整数，且

(5)

当且仅当 是素数时。

已经设计了许多素因数分解算法，用于确定给定整数的素因子，这个过程称为因式分解或素因数分解。它们的复杂性和复杂程度差异很大。构建一个通用的算法来解决这个计算上“困难”的问题非常困难，因此关于问题中的数字或其因子的任何额外信息通常可以用于节省大量时间。应该强调的是，尽管没有已知的有效算法可以分解任意整数，但尚未证明不存在这样的算法。因此，可以想象，一个足够聪明的人可以设计出一种通用的因式分解方法，这种方法将使当前广泛使用的绝大多数加密方案（包括银行和政府使用的那些）易于破解。

由于素数在RSA 加密等加密算法中的重要性，素数可能成为重要的商业商品。事实上，R. Schlafly (1994) 获得了美国专利 ，用于以下两个素数（以十六进制表示法表示）

(6)

和

(7)

算术基本定理指出，任何正整数都可以以正好一种方式表示为素数的乘积。欧几里得第二定理证明了存在无限多个素数。然而，尚不清楚是否存在无限多个形式为 的素数 (Hardy and Wright 1979, p. 19; Ribenboim 1996, pp. 206-208)，是否存在无限多个孪生素数（孪生素数猜想），或者是否总能在 和 之间找到素数 (Hardy and Wright 1979, p. 415; Ribenboim 1996, pp. 397-398)。后两个是兰道问题中的两个。

寻找因子的最简单方法是所谓的“直接搜索因式分解”（又名试除法）。在这种方法中，所有可能的因子都使用试除法进行系统地测试，以查看它们是否实际整除给定的数字。它仅适用于非常小的数字。更通用（且更复杂）的方法包括椭圆曲线因式分解法和数域筛法因式分解法。

已经证明，素数集合是一个丢番图集 (Ribenboim 1991, pp. 106-107)。

除了 2 和 3 之外，所有素数都具有 的形式，即 (Bungus 1599, p. 399, quoted in Peano 1908, p. 59; Wells 1986, p. 68)。对于整数 的 ， 是素数当且仅当同余方程

(8)

对于 、1、...、 成立 (Deutsch 1996)，其中 是一个二项式系数。此外，整数 是素数当且仅当

(9)

前几个复合 ，对于它们 是 、560、588、1400、23760、... (OEIS A011774; Guy 1997)，总共有 18 个这样的数字小于 。

Chen (1979) 表明，对于足够大的 ，在 和 之间，对于 ，总是存在一个至少有两个素因子的数字 (Le Lionnais 1983, p. 26; Guy 2004, p. 34)。实际上，这种关系似乎适用于所有 。

由连续数字组成的素数（将 0 视为在 9 之后）包括 2、3、5、7、23、67、89、4567、78901、... (OEIS A006510)。由本身是素数的数字组成的素数包括 23、37、53、73、223、227、233、257、277、337、353、373、523、557、... (OEIS A019546)，这是斯马兰达克序列之一。

由于素数 只有平凡因子 1 和 ，比尔·盖茨在他的未来之路中意外地提到了一个平凡的操作，当时他说：“由于系统的隐私和数字货币的安全性都依赖于加密，因此数学或计算机科学方面的突破如果击败了密码系统，可能会是一场灾难。明显的数学突破将是开发一种分解大素数的简单方法[重点添加]”（Gates 1995, p. 265）。