# 埃拉托色尼筛法（素数列表生成器）

用埃拉托色尼筛法生成不超过 n（≤ 10⁷）的全部素数，可选只取区间 [m, n] 内的素数。输出展示筛法机制：基素数（p² ≤ n）、划去操作次数与实际合数个数，素数列表最多显示 200 个但计数始终精确。经典例：n = 100 时以基素数 2、3、5、7 划掉 74 个合数，剩 25 个素数；π(1000) = 168。

> 标准页面: https://elysiatools.com/zh/tools/sieve-of-eratosthenes

- **分类:** Math & Numbers

- **关键词:** 埃拉托色尼筛, 素数, 素数列表, 素数生成, 素数计数, 合数, 数论

## 概述

埃拉托色尼筛法（素数列表生成器）可用于快速计算并生成指定上限 n（最高支持 10⁷）或指定闭区间 [m, n] 内的全部素数。工具不仅提供素数列表与素数计数函数值 π(n)，还会详细展示基素数（满足 p² ≤ n）、划去操作总次数及实际合数个数等底层算法机制，帮助用户深入理解数论与筛法运作过程。

## 输入项

- **上界 n** (text): Sieve bound, 2 ≤ n ≤ 10⁷ (byte-sieve limit).
- **下界 m（可选）** (text): Only list primes ≥ m; leave empty to enumerate from 2.

## 适用场景

- 需要生成不超过特定数值（如 100、1000 或更高）的完整素数列表与最大素数时
- 需要查询指定闭区间 \[m, n\] 内存在哪些素数及其精确数量时
- 学习或教学数论算法，需要直观观察基素数选取和合数划去操作次数时

## 工作原理

- 输入计算上界 n（2 ≤ n ≤ 10⁷），可选择性输入下界 m 以限定区间范围
- 算法从 2 开始确定满足 p² ≤ n 的基素数，并以此遍历划去所有合数倍数
- 统计划去操作总数与独立合数总量，计算出素数计数值 π(n)
- 输出区间内的素数列表（最多展示前 200 个）、区间素数总数及最大素数

## 使用案例

- 数学与算法教学：用于演示埃拉托色尼筛法原理与合数标记过程
- 密码学与编程测试：快速获取指定数值范围内的素数集合或寻找临界素数
- 数论作业与研究：快速核对素数计数函数 π(n) 与区间素数分布

## 常见问题

### 什么是基素数？

基素数是指满足 p² ≤ n 的所有素数。埃拉托色尼筛法只需遍历这些基素数的倍数即可划去范围内的全部合数。

### 支持的最大计算上限是多少？

上界 n 最高支持输入 10,000,000（10⁷）。

### 为什么生成的素数列表有时不展示全部结果？

当范围内素数较多时，为保持界面清晰，文本列表最多展示前 200 个素数，但素数计数统计（π 值）始终保持完全精确。

### 如果留空下界 m 会怎样？

留空下界 m 时，工具默认从最小素数 2 开始筛选并统计直至上界 n 的所有素数。

### 划去操作次数与实际合数个数为什么不同？

因为一个合数可能同时是多个基素数的倍数（例如 6 同时是 2 和 3 的倍数），会被多次重复划去，因此划去操作总次数通常大于实际合数个数。

## 相关工具

- [排列 / 组合 / 子集生成器（支持重复元素）](https://elysiatools.com/zh/tools/combinatorial-generation): 生成多重集的排列、组合与子集，自动去重并按字典序输出：排列用 next_permutation，精确计数 n!/Π(mᵢ!)；组合生成不同的 k-子多重集，计数为 Π(1+x+…+x^mᵢ) 中 x^k 的系数（元素互异时即 C(n,k)）；子集枚举所有子多重集，计数 Π(mᵢ+1)（互异时 2ⁿ），含空集。最多 12 个元素，展示上限 200 条但计数始终精确；组合模式要求 1 ≤ k ≤ n。经典例：\[A, A, B\] 的排列 → 3!/2! = 3 个（AAB、ABA、BAA）；\[A, A, B\] 的子集 → (2+1)(1+1) = 6 个。
- [三相短路电流估算计算器（IEC 60909）](https://elysiatools.com/zh/tools/short-circuit-current-calculator): 按 IEC 60909 远端短路法估算三相对称短路电流：I"_k = c·U_n/(√3·|Z|)，i_p = κ·√2·I"_k。阻抗由变压器与线路串联累加；峰值系数 κ = 1.02 + 0.98·e^(−3R/X)。
- [Carmichael 函数 λ(n) 计算器](https://elysiatools.com/zh/tools/carmichael-function): 计算 Carmichael 函数 λ(n)——乘法群 (Z/nZ)* 的指数，即使所有与 n 互素的 a 满足 a^k ≡ 1 (mod n) 的最小 k。由质因数分解按 λ(2)=1、λ(4)=2、λ(2^k)=2^(k−2)（k ≥ 3）、奇素数幂 λ(p^k)=φ(p^k) 再取 lcm 得到，同时给出 φ(n) 对比、是否存在原根，并用 Korselt 判据识别 Carmichael 数。经典例：λ(561) = 80（561 是最小的 Carmichael 数），而 λ(8) = 2 < φ(8) = 4。
- [中国剩余定理求解器（同余方程组）](https://elysiatools.com/zh/tools/chinese-remainder-theorem): 求解同余方程组 x ≡ rᵢ (mod mᵢ)（2–20 条方程），采用逐对合并的广义中国剩余定理：模数两两互素时合并模数为乘积，非互素但相容时合并模数为最小公倍数，不相容（公因数不整除余数差）则明确报告无解。每条方程都会对最终解回代验证。经典例：x ≡ 2 (mod 3)、x ≡ 3 (mod 5)、x ≡ 2 (mod 7) 的解为 x = 23 (mod 105)。
- [欧拉函数 φ(n) 计算器](https://elysiatools.com/zh/tools/euler-totient-function): 计算欧拉函数 φ(n)——\[1, n\] 中与 n 互素的正整数个数。先做试除法质因数分解，再按 φ(n) = n · Π(1 − 1/p) 精确求值（n ≤ 10¹²），可附带列出前 60 个互素数，并给出欧拉定理 a^φ(n) ≡ 1 (mod n)。经典例：φ(36) = 12（36 = 2² × 3²）；n 为素数时 φ(n) = n − 1，如 φ(97) = 96。
- [分数小数转换器](https://elysiatools.com/zh/tools/fraction-decimal-converter): 在分数和小数之间转换，支持带分数、假分数和各种小数格式
- [零和博弈求解器（鞍点 / 线性规划混合策略）](https://elysiatools.com/zh/tools/game-theory-zero-sum): 求解 2–6 × 2–6 双人零和博弈（支付矩阵归行方——最大化者，列方支付）：先做鞍点检验（行最小值的最大值 = 列最大值的最小值时存在纯策略均衡，列出所有鞍点格）；否则移位矩阵使元素 ≥ 1 后用单阶段单纯形（松弛基、Bland 规则）求解 max Σz s.t. Bz ≤ 1，其原始解给出列方混合策略 q，对偶影子价格恰为行方 LP 解 y，值移回后给出 x、q、v，并数值验证双方安全策略（xᵀA ≥ v、Aq ≤ v）与极小极大相等。经典例：猜硬币 \[\[1,-1\],\[-1,1\]\] → 值 0，双方各以 0.5/0.5 混合。
- [拉普拉斯逆变换计算器（部分分式法）](https://elysiatools.com/zh/tools/inverse-laplace-calculator): 对有理函数 F(s) = N(s)/D(s)（真分式，分母次数 ≤ 6）求拉普拉斯逆变换：先对分母求根并按重数/共轭对分组，再解多项式系数线性方程组得到部分分式分解，最后逐项查表反变换（A/(s−r)→Ae^(rt)、A/(s−r)^j→At^(j−1)e^(rt)/(j−1)!、(Bs+C)/((s−α)²+β²)→e^(αt)\[Bcos(βt)+…sin(βt)\]）。经典例：1/(s²+3s+2) → e^(−t)−e^(−2t)；(3s+5)/(s²+4) → 3cos(2t)+2.5sin(2t)。

## 示例

- [Web Python 图像处理示例](https://elysiatools.com/zh/samples/web-image-processing-python): Web Python 图像处理示例，使用 PIL/Pillow 包括读取、保存、缩放和格式转换
- [Android Java 图像处理示例](https://elysiatools.com/zh/samples/android-image-processing-java): Android Java 图像处理示例，包括图像读取保存、缩放和格式转换
- [Android Kotlin 图像处理示例](https://elysiatools.com/zh/samples/android-image-processing-kotlin): Android Kotlin 图像处理示例，包括图像读取保存、缩放和格式转换
- [Web Rust 图像处理示例](https://elysiatools.com/zh/samples/web-image-processing-rust): Web Rust 图像处理示例，包括图像读取保存、缩放和格式转换