欧几里得定理 #
素数的个数是无限的。换句话说，没有“最大的素数”。
欧几里得的论证方法是数学史上最优雅、最著名的证明之一。步骤很短：
- 假设素数只有有限多个：\( p_1,p_2,...,p_n\)
- 考虑新数：\( N = p_1p_2...p_n + 1\)
- 那么 N 不可能被这些已知的素数整除，因为除以任意都会余 1
- 因此，要么 N 本身是素数，要么 N 的某个素因子不是这份有限列表里的
- 结论：总能找到比“有限列表”之外的新素数 ⇒ 假设矛盾
- 于是，素数必须无限
证明方法是反证法的典型范例：假设有限，构造出矛盾。这种风格后来成为数学证明的核心范式。
素数定理 #
定义 \( π(x) \) 为素数计数函数，也就是小于等于x 的素数个数。例如 π(10)=4，因为共有 4 个素数小于等于 10，分别是 2、3、5、7。素数定理的叙述为：
当 x 趋近无限，π(x) 和 \( \frac {x}{\ln x} \) 的比值趋近 1。其数学式写做：
\[ \lim_{x \to \infty}\frac{π(x)}{\frac{x}{\ln x}} = 1 \]素数定理也可以被想像成描述从正整数中抽到素数的概率：从不大于 n 的正整数中随机选出一个数，它是素数的概率大约是 \({\frac {1}{\ln n}}\)。或者说在大数附近，素数之间平均相隔约 \(ln{n}\)。
Rosser定理 #
指的是第 n 个质数会大于 nlog，完整陈述如下，设质数 \( p_n \) 为第n个质数，那对于任意的 \( n \geq 1 \)而言，以下不等式成立：
\[p_{n} \gt n\ln{n}\]哥德巴赫猜想 #
1742 年，德国业余数学家 Christian Goldbach 写信给 Euler 提出想法。Euler 认为它很可能成立，并提出更强版本（偶数形式）。哥德巴赫当时并没有直接提出“每个偶数都是两个素数之和”。他写的是：每个大于 2 的整数都可以表示为三个素数之和。
欧拉在回信中重述并强化了哥德巴赫的想法：你提出的“每个整数是三个素数之和”的猜想可以化简为“每个偶数大于 2 的数是两个素数之和”。并补充说：他相信这是真的，但自己还没有办法证明。
在 18 世纪，哥德巴赫和欧拉都把 1 也算作素数
哥德巴赫猜想（Goldbach’s Conjecture）是数论中最著名、最古老的未解难题之一。它的核心思想极其简洁，却让数学家们困惑了近 300 年。
- 强猜想（也叫“偶数猜想”，是现在大家口中常说的）： 每个大于 2 的偶数都可以写成两个素数之和。至今无人完全证明，已经用计算机穷举验证到非常大的范围，也没有找到任何一个例外。
- 弱猜想（1742 年 Euler 转述）： 每个大于 5 的奇数都可以写成三个素数之和。2013 年，秘鲁数学家 Harald Helfgott 证明了弱哥德巴赫猜想。
孪生素数猜想 #
孪生素数猜想（Twin Prime Conjecture）和哥德巴赫猜想一样，是数论里最“直白但极难”的问题之一。它问的是：是否存在无穷多个孪生素数对？ 所谓孪生素数，就是差为 2 的一对素数，比如：(3, 5)，(5, 7)
换句话说：素数间隔 2 的情况，不是偶尔发生，而是会无限延续下去。
进展：
- 已经找到极大规模的孪生素数对，例如
2996863034895 × 2^1290000 ± 1都是素数，构成孪生对。 - 张益唐 (2013)：震撼成果。他证明了存在无穷多个素数对，它们的间隔至多 7000万。 这是首次证明“素数间隔有界无穷多次出现”。
- Polymath 项目 (2013–2014)：集体推进，把上界从 7000 万降低到 246。
素数间隔 #
由素数定理可知：平均间隔 ∼ lnx。
同时：
- 有时间隔极大（无限增长）。
- 有时间隔极小（可能是 2，若孪生素数猜想成立）。
- 在多项式长度的区间里必有素数存在，这是对素数稠密性的保证。目前在区间\([x, x+x^{0.525}]\) 内一定有素数。
素数筛选 #
The Sieve of Eratosthenes “埃拉托斯特尼筛法”，简称埃氏筛，一个古老而优雅的算法，用来高效找出某个范围内的所有素数。
主要依赖的思想是：从最小的素数开始，逐步剔除它的倍数，留下的数就是素数。
想要筛出 1 到 30 的素数：
- 从 2 开始，把 2 的倍数都划掉（4, 6, 8, …）。
- 下一个没被划掉的是 3，把 3 的倍数划掉（9, 12, 15, …）。
- 下一个是 5，把 5 的倍数划掉（25, 30, …）。
- 再下一个是 7，但 7^2 = 49 > 30，停止。（或者说30应该包含小于 \( \sqrt{30} \)的质因子）
剩下的就是 2, 3, 5, 7, 11, 13, 17, 19, 23, 29。
时间复杂度：O(n*loglogn)
空间复杂度：O(n)
费马素数 #
费马素数 (Fermat primes)定义为：
\[ F_{n} = 2^{2^n} + 1 \]如果 \( F_{n} \) 是素数，就称为费马素数。
从 \( F_5 = 2^{32} + 1 = 4294967297 \) 开始，就已经不是素数了（欧拉证明它能被 641 整除）
目前已知只有这 5 个费马素数，而且人们普遍相信不会再有新的费马素数了（虽然还没被证明）。
梅森素数 #
梅森素数 (Mersenne primes)定义为：
\[ M_{p} = 2^{p} - 1 \]如果 \(M_p\) 是素数，就称为梅森素数。注意：这里 p 必须是素数，否则 \(M_p\) 一定不是素数（例如 \(2^{15} − 1 = 32767 = 7 × 4681\) ）。
已知最大素数基本都是梅森素数（因为有 Lucas–Lehmer 检验可以高效验证）。梅森数的二进制形式特殊，一串 p 个 1，有利于大数模运算优化。分布式项目 GIMPS 的推动，专注于这类数。