质数筛java模板

<think>嗯，用户想了解质数筛的Java模板。首先，我得先确定他们需要的是哪种筛法。质数筛常见的有埃拉托斯特尼筛法和欧拉筛，也就是线性筛。可能用户需要的是这两种的其中一种，或者两者都介绍？ 埃拉托斯特尼筛法比较基础，时间复杂度是O(n log log n)，适合初学者。而欧拉筛是线性的O(n)，效率更高，但实现稍微复杂一些。可能需要先解释这两种方法的原理，再给出代码模板。 接下来，用户可能希望得到可以直接使用的Java代码。所以我要确保代码正确，语法没有问题。比如埃筛中，用一个布尔数组标记非质数，然后从2开始筛掉倍数。需要注意的是，j应该从i*i开始，这样可以减少重复标记。不过有些实现可能还是从2*i开始，这时候可能需要解释为什么。 对于欧拉筛，关键在于每个合数只被最小的质因数筛掉，所以需要用当前质数去乘已有的质数，当遇到能整除时停止。这部分逻辑需要详细注释，否则读者可能会不明白。 另外，用户可能需要知道这两种筛法的适用场景。比如埃筛在n较大时可能内存占用高，而欧拉筛更高效，但代码复杂。所以需要比较两者的优缺点，帮助用户选择。 还要注意代码的格式，比如变量命名是否清晰，循环的范围是否正确。例如，埃筛的外层循环只需要到sqrt(n)就可以了，但通常实现中还是循环到n，因为内部的j会从i*i开始，超过n时就不会进入循环了。 然后，测试用例也是重要的，比如在main函数里调用筛法函数，输出结果是否正确。例如，当n=30时，应该输出所有质数到30为止。这能帮助用户验证代码的正确性。 用户可能还会有疑问，比如如何处理大数情况下的效率问题，或者内存限制。比如埃筛的空间复杂度是O(n)，当n到1e8时可能需要考虑内存，而欧拉筛同样需要O(n)的空间，但时间更优。 还有可能遇到的问题，比如数组越界，或者在标记时的重复操作。比如埃筛中，当i是质数时，才需要标记其倍数，否则跳过。这点需要代码中的条件判断正确。 总结下来，我需要分步骤介绍两种筛法，给出代码模板，并解释关键部分，同时比较它们的优缺点，帮助用户理解如何选择和使用。</think>### 质数筛 Java 模板分步解析 质数筛法用于高效筛选范围内的质数，以下是两种常见筛法的实现模板及原理说明： --- #### 1. **埃拉托斯特尼筛法 (Eratosthenes)** **核心思想**：标记非质数，时间复杂度 O(n log log n) **适用场景**：数据规模中等（例如 n ≤ 1e7） ```java public class PrimeSieve { public static List<Integer> sieveOfEratosthenes(int n) { boolean[] isPrime = new boolean[n + 1]; Arrays.fill(isPrime, true); isPrime[0] = isPrime[1] = false; // 0和1不是质数 for (int i = 2; i * i <= n; i++) { if (isPrime[i]) { // 标记i的倍数为非质数 for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } // 收集所有质数 List<Integer> primes = new ArrayList<>(); for (int i = 2; i <= n; i++) { if (isPrime[i]) { primes.add(i); } } return primes; } public static void main(String[] args) { int n = 30; List<Integer> primes = sieveOfEratosthenes(n); System.out.println("质数列表：" + primes); } } ``` **关键点说明**： - 外层循环只需遍历到 $\sqrt{n}$（优化点） - 内层循环从 $i^2$ 开始标记，避免重复操作（如当 $i=2$ 时，已标记过 $4,6,8$，后续无需重复） - 空间复杂度为 $O(n)$ --- #### 2. **欧拉筛（线性筛）** **核心思想**：每个合数只被最小质因数筛除，时间复杂度 O(n) **适用场景**：数据规模较大（例如 n ≤ 1e8） ```java public class EulerSieve { public static List<Integer> eulerSieve(int n) { boolean[] isPrime = new boolean[n + 1]; Arrays.fill(isPrime, true); List<Integer> primes = new ArrayList<>(); for (int i = 2; i <= n; i++) { if (isPrime[i]) { primes.add(i); // 记录质数 } // 用当前质数筛选合数 for (int j = 0; j < primes.size() && primes.get(j) * i <= n; j++) { isPrime[primes.get(j) * i] = false; if (i % primes.get(j) == 0) { break; // 保证每个数只被最小质因数筛除 } } } return primes; } public static void main(String[] args) { int n = 30; List<Integer> primes = eulerSieve(n); System.out.println("质数列表：" + primes); } } ``` **关键点说明**： - 使用 `primes` 列表动态存储已知质数 - 通过 `i % primes.get(j) == 0` 终止循环，确保每个合数只被标记一次 - 适用于需要多次查询质数的场景 --- #### 两种筛法的对比 | 特性 | 埃拉托斯特尼筛法 | 欧拉筛 | |--------------------|------------------------|--------------------| | **时间复杂度** | $O(n \log \log n)$ | $O(n)$ | | **空间复杂度** | $O(n)$ | $O(n)$ | | **优势** | 实现简单 | 效率更高 | | **适用场景** | 单次查询或中等规模数据 | 大规模数据或高频调用 | --- #### 使用建议 - 若需快速实现，优先选择 **埃拉托斯特尼筛法** - 若对性能要求高（如竞赛或大数据场景），使用 **欧拉筛**