埃氏筛（Sieve of Eratosthenes）是一种古老且高效的算法，用于找出一定范围内（例如 2 到 n 之间）的所有质数（素数）。
它的核心思想非常简单而巧妙：不是直接去找质数，而是先把所有的数都列出来，然后系统地划掉（排除）合数，最后剩下的就是质数。
算法步骤详解
- 创建列表： 创建一个从 2 到 n 的连续整数列表。这个列表代表了所有候选数。
- 初始化： 令最小的未标记数（最初是 2）为
p。p 一定是质数。
- 标记合数： 从
p² 开始，将列表中所有 p 的倍数（p², p² + p, p² + 2p, ...）标记为合数（例如划掉或置为 False）。
- 为什么从
p² 开始？ 因为更小的倍数（如 2p, 3p, ..., (p-1)p）肯定已经被比 p 更小的质数（例如 2, 3, ..., p-1）标记过了。从 p² 开始标记避免了重复工作。
- 寻找下一个
p： 找到列表中下一个大于 p 的、未被标记为合数的数。这个数就是下一个质数，将其作为新的 p。
- 重复： 重复步骤 3（标记新
p 的倍数）和步骤 4（找下一个 p），直到 p² 大于 n。
- 为什么
p² > n 就停止？ 因为对于当前的 p，它的最小未标记倍数 p² 已经超出了我们考虑的范围 n。更重要的是，所有小于等于 n 的合数，其最小的质因数必然小于等于 √n。所以当 p > √n 时，所有小于等于 n 的合数肯定已经被小于等于 √n 的质数标记过了。继续找更大的 p 并标记其倍数就是徒劳的（这些倍数本身也大于 n）。
- 输出结果： 当算法终止时，列表中所有未被标记为合数的数就是 2 到 n 之间的所有质数。
示例（找出 2 到 30 之间的质数）
- 创建列表：
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
- 第一个
p = 2（质数）。
- 标记
2² = 4 开始的 2 的倍数：4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30。
- 下一个未标记数是
3（质数）。
- 标记
3² = 9 开始的 3 的倍数：9, 12, 15, 18, 21, 24, 27, 30。（注意 6, 12, 18 等已被标记过）。
- 下一个未标记数是
5（质数）。
- 标记
5² = 25 开始的 5 的倍数：25, 30。（10, 15, 20 等已被标记过）。
- 下一个未标记数是
7（质数）。
- 下一个未标记数是
11（质数）。
- 后续未标记数
13, 17, 19, 23, 29 都是质数，且它们的平方都大于 30。
- 最终未被标记的数（质数）：
2, 3, 5, 7, 11, 13, 17, 19, 23, 29。
时间复杂度
埃氏筛的时间复杂度是 O(n log log n)。这比使用试除法（逐个检查每个数是否是质数，时间复杂度约为 O(n√n) 或 O(n²)）要高效得多，尤其当 n 很大时。
优点
- 高效： 时间复杂度 O(n log log n) 使其成为找出小到中等规模范围内所有质数的首选方法。
- 简单直观： 算法原理和实现相对容易理解。
- 空间换时间： 使用一个布尔数组来标记，空间复杂度 O(n)，在现代计算机上通常可以接受。
缺点
- 空间占用： 需要 O(n) 的空间存储标记数组。当 n 极大（例如数十亿）时，这可能会成为瓶颈。
- 缓存不友好： 标记大质数的倍数时，跳跃范围很大，可能导致较多的缓存未命中，影响速度。
- 存在更优筛法： 对于极大的 n，欧拉筛（线性筛）时间复杂度 O(n)，空间复杂度 O(n)，在理论上更优，但实现稍复杂。
优化
- 仅筛选奇数： 除了 2，所有偶数都不是质数。可以只创建奇数列表（从 3 开始），空间和标记工作量减半。
- 位级压缩： 使用位图（Bit Array）代替布尔数组，空间占用可减少到 O(n / 8) 或 O(n / 32)（取决于系统字长）。
- 分段筛选： 将大范围分成小段依次筛选，突破内存限制。
总结
埃氏筛是一种通过系统地标记并排除合数来找出给定范围内所有质数的经典算法。它以其相对简单、高效（O(n log log n)）而闻名，是解决寻找质数列表问题的强大工具，特别适用于 n 在数百万到数亿级别的情况。理解其“标记合数”的核心思想和“从 p² 开始标记”的优化点是掌握该算法的关键。
欧拉函数（Euler's totient function），通常记作 φ(n) 或 ϕ(n)，是数论中一个非常重要的函数。它的定义是：
φ(n) 表示小于或等于正整数 n 的数中，与 n 互质的数的个数。
核心概念解释
互质 (Coprime)：
- 如果两个正整数 a 和 b 的最大公约数 (GCD) 为 1，即
gcd(a, b) = 1，则称 a 和 b 互质。
- 例如，
gcd(9, 4) = 1，所以 9 和 4 互质。gcd(8, 12) = 4 ≠ 1，所以 8 和 12 不互质。
函数值 φ(n)：
- 计算范围：1 到 n（包含 1 和 n）。
- 统计对象：在这个范围内，所有满足
gcd(k, n) = 1 的整数 k 的个数。
- 特别规定：φ(1) = 1。（因为 1 和 1 的最大公约数是 1）。
计算欧拉函数 φ(n)
计算 φ(n) 的关键在于 正整数 n 的质因数分解。有以下公式：
如果 n 是质数 (p)：
- 那么小于等于 p 的数中，除了 p 本身，其他所有数 (1, 2, ..., p-1) 都与 p 互质。
- φ(p) = p - 1
- 例如：φ(7) = 6 (1, 2, 3, 4, 5, 6 都与 7 互质)。
如果 n 是质数的幂 (pᵏ, k ≥ 1)：
- 在 1 到 pᵏ 之间，与 pᵏ 不互质的数就是那些能被 p 整除的数，即 p, 2p, 3p, ..., pᵏ⁻¹ * p。这样的数共有 pᵏ⁻¹ 个。
- 所以互质的数有
pᵏ - pᵏ⁻¹ 个。
- φ(pᵏ) = pᵏ - pᵏ⁻¹ = pᵏ (1 - 1/p)
- 例如：φ(8) = φ(2³) = 2³ - 2² = 8 - 4 = 4 (1, 3, 5, 7 与 8 互质)。φ(9) = φ(3²) = 3² - 3¹ = 9 - 3 = 6 (1, 2, 4, 5, 7, 8 与 9 互质)。
如果 n 是两个互质数 m 和 n 的乘积 (n = m * n, 且 gcd(m, n) = 1)：
- 欧拉函数具有积性 (Multiplicative)：如果两个正整数 m 和 n 互质，那么
φ(m * n) = φ(m) * φ(n)。
一般公式 (基于质因数分解)：
- 将任意正整数 n 分解为其质因数的幂的乘积：
n = p₁ᵏ¹ * p₂ᵏ² * ... * pᵣᵏʳ
(其中 p₁, p₂, ..., pᵣ 是互不相同的质数，k₁, k₂, ..., kᵣ 是正整数)。
- 利用积性和质数幂的公式，得到欧拉函数的通用计算公式：
φ(n) = n * (1 - 1/p₁) * (1 - 1/p₂) * ... * (1 - 1/pᵣ)
- 计算步骤：
- 对 n 进行质因数分解。
- 对于 n 的每一个不同的质因数 pᵢ，将 n 乘以
(1 - 1/pᵢ)。
- 对所有不同的质因数都做一次这样的乘法。
例子
n = 10:
- 质因数分解：
10 = 2¹ * 5¹
- φ(10) = 10 * (1 - 1/2) * (1 - 1/5) = 10 * (1/2) * (4/5) = 10 * 0.5 * 0.8 = 4
- 验证：小于等于 10 的数中，与 10 互质的有 1, 3, 7, 9 (共 4 个)。
n = 12:
- 质因数分解：
12 = 2² * 3¹
- φ(12) = 12 * (1 - 1/2) * (1 - 1/3) = 12 * (1/2) * (2/3) = 12 * (1/3) = 4
- 验证：与 12 互质的有 1, 5, 7, 11 (共 4 个)。
n = 36:
- 质因数分解：
36 = 2² * 3²
- φ(36) = 36 * (1 - 1/2) * (1 - 1/3) = 36 * (1/2) * (2/3) = 36 * (1/3) = 12
- 验证：与 36 互质的有 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35 (共 12 个)。
重要性质和应用
欧拉定理 (Euler's Theorem)： 这是欧拉函数最著名的应用。
- 如果正整数 a 和 n 互质（即
gcd(a, n) = 1），那么有：
aᵠ⁽ⁿ⁾ ≡ 1 (mod n)
- 这个定理是 费马小定理 (Fermat's Little Theorem) 的推广（费马小定理是欧拉定理在 n 为质数时的特例：如果 p 是质数且
gcd(a, p)=1，则 aᵖ⁻¹ ≡ 1 (mod p)）。
- 应用： 欧拉定理是现代公钥密码学（尤其是 RSA 加密算法）的核心数学基础之一。RSA 的加密和解密过程以及密钥对的生成都直接依赖于欧拉定理和欧拉函数的计算。
模 n 的既约剩余系 (Reduced Residue System Modulo n)：
- 所有小于 n 且与 n 互质的正整数组成的集合，称为模 n 的一个既约剩余系。
- 这个集合的元素个数恰好等于 φ(n)。
与因子和的关系： Σ φ(d) = n，其中求和是对 n 的所有正因子 d 进行的。例如，n=6 的因子是 1, 2, 3, 6：φ(1) + φ(2) + φ(3) + φ(6) = 1 + 1 + 2 + 2 = 6。
总结
欧拉函数 φ(n) 计算的是在 1 到 n 的整数中，与 n 互质的数的个数。它的计算依赖于 n 的质因数分解，核心公式是 φ(n) = n * Π(1 - 1/pᵢ)（pᵢ 取遍 n 的所有不同的质因数）。欧拉函数在数论中具有基础性地位，其最重要的应用体现在欧拉定理上，该定理是 RSA 公钥密码体系等现代加密技术的基石。理解欧拉函数是理解这些重要数学理论和应用的关键。
欧拉定理（Euler's Theorem） 和 费马小定理（Fermat's Little Theorem） 是数论中两个核心定理，它们在模运算和密码学中至关重要。以下是它们的定义、联系以及在求幂取模中减少时间复杂度的原理：
1. 费马小定理（Fermat's Little Theorem）
- 适用条件：
- ( p ) 是一个质数。
- ( a ) 是任意整数，且 ( p \nmid a )（即 ( a ) 不是 ( p ) 的倍数）。
- 定理内容：
[
a^{p-1} \equiv 1 \pmod{p}
]
- 推论：
[
ap \equiv a \pmod{p} \quad (\text{对任意整数 } a \text{ 成立，无需 } p \nmid a)
]
- 示例：
- 计算 ( 5^{6} \mod 7 )（( p=7 ) 是质数）：
[
5^{6} = (5^{7-1}) \equiv 1 \pmod{7}
]
直接得结果为 ( 1 )。
2. 欧拉定理（Euler's Theorem）
- 适用条件：
- ( n ) 是任意正整数。
- ( a ) 是整数，且 ( \gcd(a, n) = 1 )（即 ( a ) 与 ( n ) 互质）。
- 定理内容：
[
a^{\phi(n)} \equiv 1 \pmod{n}
]
其中 ( \phi(n) ) 是欧拉函数（小于等于 ( n ) 且与 ( n ) 互质的数的个数）。
- 与费马小定理的关系：
当 ( n = p )（质数）时，( \phi(p) = p-1 )，欧拉定理退化为费马小定理。
- 示例：
- 计算 ( 3^{4} \mod 10 )（( n=10 )，( \phi(10)=4 )，( \gcd(3,10)=1 ))：
[
3^{4} \equiv 1 \pmod{10}
]
直接得结果为 ( 1 ).
3. 为什么能减少求幂取模的时间复杂度？
在计算 ( ak \mod n )（尤其是 ( k ) 极大时，如 ( k = 10^{100} )），直接计算不可行。利用欧拉定理或费马小定理，可将指数 ( k ) 大幅缩小：
步骤：
缩小指数：
- 若 ( \gcd(a, n) = 1 )（满足欧拉定理条件），则：
[
ak = a^{k \mod \phi(n)} \cdot \left(a^{\phi(n)}\right)^{\lfloor k / \phi(n) \rfloor} \equiv a^{k \mod \phi(n)} \cdot 1^{\lfloor k / \phi(n) \rfloor} \equiv a^{k \mod \phi(n)} \pmod{n}
]
即只需计算 ( a^{(k \mod \phi(n))} \mod n )。
- 若 ( n ) 是质数（满足费马小定理条件），则指数缩小为 ( k \mod (n-1) )。
结合快速幂算法：
- 对缩小后的指数 ( r = k \mod \phi(n) )（或 ( k \mod (n-1) ))，使用快速幂算法（二进制分解）计算 ( ar \mod n )。
- 快速幂的时间复杂度为 ( O(\log r) )，而 ( r \leq \phi(n) \ll k )（( k ) 可能极大）。
时间复杂度对比：
| 方法 | 直接计算 ( ak \mod n ) | 欧拉/费马 + 快速幂 |
|------------------|-------------------------------|---------------------------|
| 时间复杂度 | ( O(k) )（不可行） | ( O(\log \phi(n)) ) |
| 关键操作 | 循环 ( k ) 次乘法 | 循环 ( \log r ) 次乘法 |
示例：
计算 ( 7^{100} \mod 5 )：
- 费马小定理（( p=5 )）：
( \phi(5)=4 )，指数缩小为 ( 100 \mod 4 = 0 )。
( 7^{100} \equiv 7^{0} \equiv 1 \pmod{5} )（无需实际计算 ( 7^{100} )）。
计算 ( 3^{100} \mod 8 )：
- 欧拉定理（( n=8 )，( \phi(8)=4 )，( \gcd(3,8)=1 ))：
指数缩小为 ( 100 \mod 4 = 0 )。
( 3^{100} \equiv 3^{0} \equiv 1 \pmod{8} ).
4. 注意事项
- 互质条件：
- 欧拉定理要求 ( \gcd(a, n) = 1 )。若不满足（如 ( a ) 与 ( n ) 有公因子），需特殊处理（如分解 ( n )）。
- ( n ) 为质数：
- 优先用费马小定理（指数缩小至 ( \mod (n-1) )），计算更简单。
- 密码学应用：
- RSA 算法的核心依赖欧拉定理：加密/解密过程本质是求 ( me \mod n )（( m ) 为明文，( e ) 为大指数）。
总结
| 定理 | 费马小定理 | 欧拉定理 |
|------------------|----------------------------------|-----------------------------------|
| 适用场景 | ( n ) 为质数 | ( n ) 任意，且 ( \gcd(a,n)=1 ) |
| 指数缩小规则 | ( k \to k \mod (n-1) ) | ( k \to k \mod \phi(n) ) |
| 优化效果 | 将指数 ( k ) 从天文数字降至 ( <n ) | 同左 |
通过将指数 ( k ) 缩小到 ( \phi(n) )（或 ( n-1 )) 的范围内，再结合快速幂算法，可将计算复杂度从 不可行（( O(k) )）降至 高效（( O(\log \phi(n)) )），这是处理大数模幂运算的核心技巧。
欧拉定理的证明
欧拉定理：若正整数 (a) 与 (n) 互质（即 (\gcd(a, n) = 1)），则
[
a^{\phi(n)} \equiv 1 \pmod{n}
]
其中 (\phi(n)) 是欧拉函数（小于等于 (n) 且与 (n) 互质的数的个数）。
证明思路（群论与数论结合）：
构造既约剩余系：
设 (R = { r_1, r_2, \dots, r_{\phi(n)} }) 是模 (n) 的一个既约剩余系（即所有与 (n) 互质且模 (n) 不同余的整数集合，通常取 (1 \leq r_i \leq n)）。
构造新集合 (S)：
定义集合 (S = { a \cdot r_1, a \cdot r_2, \dots, a \cdot r_{\phi(n)} })。
- 由于 (\gcd(a, n) = 1) 且 (\gcd(r_i, n) = 1)，有 (\gcd(a \cdot r_i, n) = 1)。
- 若 (a \cdot r_i \equiv a \cdot r_j \pmod{n})，则因 (\gcd(a, n) = 1)，可消去 (a) 得 (r_i \equiv r_j \pmod{n})，矛盾。
结论：(S) 也是模 (n) 的一个既约剩余系。
乘积相等：
比较 (R) 和 (S) 中所有元素的乘积：
[
\prod{i=1}^{\phi(n)} r_i \equiv \prod{i=1}^{\phi(n)} (a \cdot r_i) = a^{\phi(n)} \cdot \prod_{i=1}^{\phi(n)} r_i \pmod{n}
]
消去互质因子：
令 (P = \prod_{i=1}^{\phi(n)} r_i)。由上式：
[
P \equiv a^{\phi(n)} \cdot P \pmod{n}
]
因 (\gcd(P, n) = 1)（(P) 是既约剩余系元素的乘积），可在模 (n) 下消去 (P)：
[
a^{\phi(n)} \equiv 1 \pmod{n}
]
欧拉定理的推广
1. 卡迈克尔函数（Carmichael Function）
定义：(\lambda(n)) 是满足以下条件的最小正整数 (m)：
[
am \equiv 1 \pmod{n}, \quad \forall a \text{ 满足 } \gcd(a, n) = 1.
]
性质：
(\lambda(n) \mid \phi(n))（卡迈克尔函数的值整除欧拉函数值）。
当 (n = pk)（(p) 为奇素数）：
[
\lambda(pk) = \phi(pk) = p^{k-1}(p-1).
]
当 (n = 2k)：
[
\lambda(2) = 1, \quad \lambda(4) = 2, \quad \lambda(2k) = 2^{k-2} \ (k \geq 3).
]
一般 (n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r})：
[
\lambda(n) = \operatorname{lcm}[\lambda(p_1^{k_1}), \lambda(p_2^{k_2}), \dots, \lambda(p_r^{k_r})].
]
推广的欧拉定理：
[
a^{\lambda(n)} \equiv 1 \pmod{n}, \quad \gcd(a, n) = 1.
]
意义：(\lambda(n)) 是比 (\phi(n)) 更精确的“最小通用指数”。
2. 指数循环公式（不要求互质）
定理：对任意整数 (a) 和 (n \geq 2)，若 (k \geq \phi(n))，则
[
ak \equiv a^{k \mod \phi(n) + \phi(n)} \pmod{n}.
]
证明思路：
对 (n) 的每个素因子幂 (pe) 分别证明同余式。
若 (\gcd(a, pe) = 1)，用欧拉定理；若 (\gcd(a, pe) \neq 1)，利用 (a^{\phi(n)} \equiv 0 \pmod{pe})（因 (p \mid a)）。
最后用中国剩余定理合并。
应用：计算大指数模运算（如 (a^{10^{100}} \mod n)），无需 (\gcd(a, n) = 1)。
示例：
计算 (7^{100} \mod 10)：
(\phi(10) = 4)，
(100 \mod 4 = 0)，故
(7^{100} \equiv 7^{0 + 4} = 74 \equiv 2401 \equiv 1 \pmod{10})。
3. 群论推广（有限群中的拉格朗日定理）
定理：在有限群 (G) 中，任意元素 (g) 的阶 (d) 满足 (d \mid |G|)（(|G|) 是群的阶）。
与欧拉定理的联系：
- 取 (G = (\mathbb{Z}/n\mathbb{Z})\times)（模 (n) 的乘法群），则 (|G| = \phi(n))。
- 元素 (a \in G) 的阶 (d) 满足 (d \mid \phi(n))，故 (a^{\phi(n)} = (ad)^{\phi(n)/d} = 1^{\phi(n)/d} = 1)。
4. 多项式环上的推广
定理：在多项式环 (\mathbb{F}_q[x])（(q) 为素数幂）中，若多项式 (f(x)) 与 (g(x)) 互质，则
[
g(x)^{\phi(f)} \equiv 1 \pmod{f(x)},
]
其中 (\phi(f)) 是模 (f(x)) 的既约多项式剩余系大小（类比整数欧拉函数）。
总结
| 推广方向 | 核心公式 | 应用场景 |
|------------------------|---------------------------------------------|----------------------------------|
| 卡迈克尔函数 | (a^{\lambda(n)} \equiv 1 \pmod{n}) | 密码学（优化指数大小） |
| 指数循环公式（非互质） | (ak \equiv a^{k \mod \phi(n) + \phi(n)} \pmod{n}) | 大数模幂计算（如编程竞赛） |
| 有限群中的拉格朗日定理 | (g^{|G|} = 1) | 抽象代数、密码学理论 |
| 多项式环推广 | (g(x)^{\phi(f)} \equiv 1 \pmod{f(x)}) | 编码理论、纠错码设计 |
这些推广深化了欧拉定理的应用范围，使其成为数论、抽象代数和计算科学的核心工具。