分析素数

通过选择和应用适当的算法来分析素数：素性测试、整数分解或素数分布分析。计算验证结果并将发现与素数定理相关联。

适用场景

• 判断给定整数是否为素数或合数
• 查找整数的完整素因数分解
• 计数或列出给定上界以内的素数
• 验证素数定理在特定范围内的近似精度
• 在数论证明或计算中研究素数性质

输入

• 必需：待分析的整数或分布分析的上界
• 必需：任务类型——以下之一：素性测试、分解或分布分析
• 可选：首选算法（试除法、Miller-Rabin、埃拉托斯特尼筛法、Pollard's rho）
• 可选：是否需要正式的素性证明还是仅计算判定
• 可选：输出格式（因子树、素数列表、计数、表格）

步骤

第 1 步：确定任务类型

将请求分类为三类之一并选择适当的算法路径。

1. 素性测试：给定单个整数 n，判断 n 是否为素数。
2. 分解：给定合数 n，找到其完整的素因数分解。
3. 分布分析：给定上界 N，分析 N 以内的素数（计数、列表、间隔、密度）。

记录任务类型和输入值。

预期结果： 明确的分类及记录的输入值。

失败处理： 如果输入不明确（例如"分析 60"），请用户澄清需要素性测试、分解还是分布分析。对合数默认进行分解，对疑似素数默认进行素性确认。

第 2 步：应用素性测试（如果任务 = 素性测试）

使用与 n 的大小匹配的算法测试 n 是否为素数。

1. 处理平凡情况：n < 2 不是素数。n = 2 或 n = 3 是素数。如果 n 是偶数且 n > 2，它是合数。

2. 小 n（n < 10^6）：使用试除法。

   • 对所有 p 到 floor(sqrt(n)) 的素数测试整除性。
   • 优化：测试 2，然后是奇数 3, 5, 7, ... 或使用 6k +/- 1 轮子。
   • 如果没有找到因子，n 是素数。

3. 大 n（n >= 10^6）：使用 Miller-Rabin 概率测试。

   • 将 n - 1 写成 2^s * d 形式，其中 d 为奇数。
   • 对每个见证值 a 在 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} 中：
     • 计算 x = a^d mod n。
     • 如果 x = 1 或 x = n - 1，此见证通过。
     • 否则，将 x 平方至多 s - 1 次。如果 x 等于 n - 1，通过。
     • 如果未通过，n 是合数（a 是见证值）。
   • 对于 n < 3.317 * 10^24，见证值 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} 给出确定性结果。

4. 记录判定：素数或合数，附见证值或证书。

小素数参考（前 25 个）：

索引	素数	索引	素数	索引	素数
1	2	10	29	19	67
2	3	11	31	20	71
3	5	12	37	21	73
4	7	13	41	22	79
5	11	14	43	23	83
6	13	15	47	24	89
7	17	16	53	25	97
8	19	17	59
9	23	18	61

预期结果： 使用的算法和找到的见证值或因子的确定性答案（素数或合数）。

失败处理： 如果 Miller-Rabin 报告"可能是素数"但需要确定性，升级到确定性测试（例如 AKS 或 ECPP）。对于试除法，如果计算太慢，切换到 Miller-Rabin。

第 3 步：应用分解（如果任务 = 分解）

将 n 完全分解为其素数幂分解。

1. 通过试除法提取小因子：

   • 尽可能多次除以 2，记录指数。
   • 除以奇素数 3, 5, 7, 11, ... 直到截止值（例如 10^4 或如果 n 较小则到 sqrt(n)）。
   • 每次除法后，更新 n 为剩余的辅因子。

2. 如果辅因子 > 1 且辅因子 < 10^12：继续试除法到 sqrt(辅因子)。

3. 如果辅因子 > 1 且辅因子 >= 10^12：应用 Pollard's rho 算法。

   • 选择 f(x) = x^2 + c (mod n)，c 为随机数。
   • 使用 Floyd 循环检测：x = f(x)，y = f(f(y))。
   • 每步计算 d = gcd(|x - y|, n)。
   • 如果 1 < d < n，d 是非平凡因子。对 d 和 n/d 递归。
   • 如果 d = n，用不同的 c 重试。

4. 验证：将所有找到的素因子（含指数）相乘，确认乘积等于原始 n。测试每个因子的素性。

5. 以标准形式呈现结果：n = p1^a1 * p2^a2 * ... * pk^ak，其中 p1 < p2 < ... < pk。

算法复杂度说明：

算法	复杂度	最适用于
试除法	O(sqrt(n))	n < 10^12
Pollard's rho	O(n^{1/4}) 期望	n 到 ~10^18
二次筛法	L(n)^{1+o(1)}	n 到 ~10^50
GNFS	L(n)^{(64/9)^{1/3}+o(1)}	n > 10^50

预期结果： 标准形式的完整素因数分解，经乘法验证。

失败处理： 如果 Pollard's rho 经过多次迭代后未能找到因子（检测到循环但无非平凡 gcd），尝试不同的 c 值（至少 5 次尝试）。如果全部失败，辅因子可能是素数——用素性测试确认。

第 4 步：应用分布分析（如果任务 = 分布分析）

分析给定上界 N 以内的素数分布。

1. 使用埃拉托斯特尼筛法生成素数：

   • 创建大小为 N + 1 的布尔数组，初始化为 true。
   • 将索引 0 和 1 设为 false（非素数）。
   • 对每个 p 从 2 到 floor(sqrt(N))：
     • 如果 p 仍标记为 true，将所有倍数 p^2, p^2 + p, p^2 + 2p, ... 标记为 false。
   • 收集所有仍标记为 true 的索引。

2. 计数素数：计算 pi(N) = N 以内的素数个数。

3. 与素数定理比较：

   • PNT 近似：pi(N) ~ N / ln(N)。
   • 对数积分近似：Li(N) = 从 2 到 N 的 1/ln(t) dt 积分。
   • 计算相对误差：|pi(N) - N/ln(N)| / pi(N)。

4. 分析素数间隔（可选）：

   • 计算连续素数之间的间隔。
   • 报告最大间隔、平均间隔和孪生素数（间隔 = 2）。
   • N 附近的平均间隔约为 ln(N)。

5. 以汇总表呈现发现：

Bound N:       1,000,000
pi(N):         78,498
N/ln(N):       72,382
Li(N):         78,628
Relative error (N/ln(N)):  7.79%
Relative error (Li(N)):    0.17%
Max prime gap:  148 (between 492113 and 492227)
Twin primes:    8,169 pairs

预期结果： 附有 PNT 比较和可选间隔分析的素数计数。

失败处理： 如果 N 太大无法在内存中筛选（N > 10^9），使用分段筛法按块处理范围。如果只需要计数（不需要列表），直接使用 Meissel-Lehmer 算法计算 pi(N)。

第 5 步：计算验证结果

使用独立的计算方法交叉检验所有结果。

1. 对于素性测试：如果使用了试除法，用快速 Miller-Rabin 验证（反之亦然）。对于已知素数，对照已发表的素数表或 OEIS 序列检查。

2. 对于分解：将所有因子相乘并确认等于原始输入。独立测试每个声称的素因子的素性。

3. 对于分布：从筛法输出中抽查 3-5 个数进行素性测试。将 pi(N) 与标准基准的已发表值比较（pi(10^k)，k = 1, ..., 9）。

pi(N) 的已发表值：

N	pi(N)
10	4
100	25
1,000	168
10,000	1,229
100,000	9,592
10^6	78,498
10^7	664,579
10^8	5,761,455
10^9	50,847,534

4. 记录验证：使用的方法和结果。

预期结果： 所有结果经独立验证，无差异。

失败处理： 如果验证发现差异，启用额外检查重新运行原始计算（例如详细试除法日志）。最常见的错误是筛法边界的差一错误、模运算中的整数溢出，以及将伪素数误认为素数。

验证清单

• 任务类型正确分类（素性测试、分解或分布分析）
• 算法适合输入规模
• 平凡情况（n < 2、n = 2、偶数 n）在通用算法之前处理
• 素性判定是确定性的（不是无限定的"可能是素数"）
• 分解结果相乘等于原始数
• 每个声称的素因子都经过素性测试
• 筛法边界包含标记合数的 sqrt(N) 覆盖
• PNT 比较使用正确的公式（N/ln(N) 或 Li(N)）
• 结果通过独立方法或对照已发表值进行验证
• 边界情况（n = 0、1、2、负数输入）已处理

常见问题

• 忘记 n = 1 不是素数：按约定，1 既不是素数也不是合数。许多算法会静默地错误分类它

• 模幂运算中的整数溢出：在 Miller-Rabin 中计算 a^d mod n 时，朴素幂运算会溢出。使用模幂运算（每步带 mod 的重复平方）

• 筛法差一错误：筛法必须从 p^2 开始标记合数，而非从 2p 开始。从 2p 开始浪费时间但结果正确；从 p+1 开始则是错误的

• Pollard's rho 循环中 d = n：如果 gcd(|x - y|, n) = n，算法找到了平凡因子。用不同的多项式常数 c 重试，而不仅是不同的起始点

• Carmichael 数欺骗费马测试：像 561 = 3 * 11 * 17 这样的数对所有互素基通过费马素性测试。始终使用 Miller-Rabin，而非朴素费马测试

• 混淆 pi(n) 与常数 pi：素数计数函数 pi(n) 和圆周率 3.14159... 共享符号。上下文必须无歧义

相关技能

• solve-modular-arithmetic

  — 模运算是 Miller-Rabin 和许多分解方法的基础

• explore-diophantine-equations

  — 素因数分解是求解许多丢番图方程的前提

• formulate-quantum-problem

  — Shor 算法用于整数分解，将素数与量子计算联系起来