# Analyze Prime Numbers

> 使用素性测试、分解算法、素数分布分析和筛法分析素数。涵盖试除法、Miller-Rabin、 埃拉托斯特尼筛法和素数定理。适用于判断一个整数是否为素数或合数、查找素因数分解、 计数或列出某个上界以内的素数，或在数论证明或计算中研究素数性质时。

- Skill: `pjt222/analyze-prime-numbers-4` (Agent Skill)
- Install (CLI): `npx get-skill add pjt222/analyze-prime-numbers-4`
- Raw SKILL.md: https://api.skillmd.com/api/skills/pjt222/analyze-prime-numbers-4/raw
- Safety review: pending (external: skill-scanner PASS, skillspector PASS)
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: Coding & Dev Tools
- License: MIT
- Author: pjt222 (https://skillmd.com/u/pjt222)
- Updated: 2026-09-21
- Page: https://skillmd.com/skills/pjt222/analyze-prime-numbers-4

---


# 分析素数

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

## 适用场景

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

## 输入

- **必需**：待分析的整数或分布分析的上界
- **必需**：任务类型——以下之一：素性测试、分解或分布分析
- **可选**：首选算法（试除法、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. **以汇总表呈现发现**：

```text
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 算法用于整数分解，将素数与量子计算联系起来

