C++ 中分段筛（打印范围内的素数）

在本文中，我们将讨论 C++ 中的分段筛法（打印给定范围内的素数）。分段筛法是普通筛法算法的优化版本。与普通筛法计算每个此类数字的所有倍数不同，分段筛法仅计算在一定限制内计算出的一些素数的倍数。

分段筛法算法适用于给定范围内的所有大数，建议在搜索素数时使用。当前工作通过将范围划分为较小的块并利用先前计算出的素数来识别这些分区中的非素数来扩展埃拉托斯特尼筛法。

本文重点解释和实现分段筛法算法及其在 C++ 中的应用。

以下是分段筛法算法的步骤。

• 定义范围： 确定我们将在哪个区间 [low, high] 中寻找素数。
• 埃拉托斯特尼筛法： 在执行步骤中，我们应该应用埃拉托斯特尼筛法算法来识别不大于 high 的平方根的素数。这些素数可以帮助划掉范围内的非素数。
• 段初始化： 为范围 [low, high] 初始化一个布尔数组，所有数字都设置为 true，因为最初所有数字都被认为是素数。
• 标记非素数： 对于上面第 2 步中找到的每个素数，划掉该素数在段中的倍数。
• 输出素数： 被标记为素数的数字就是该范围内的输出。

示例

让我们举一个例子来说明 C++ 中的分段筛法（打印给定范围内的素数）。

输出

Enter the range (low high): 10 100
11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97   

说明

这个 C++ 程序使用分段筛法算法来计算和显示 [low, high] 范围内的所有素数。首先，让第一个 函数 simpleSieveNum，其工作基于埃拉托斯特尼筛法，旨在获取所有小于或等于 high 的平方根的素数。此函数以跟踪数字素数的方式开发一个名为 mark_Sieves 的布尔 数组，其中非素数设置为 false。素数累积在名为 primeNum 的 向量 类型的数组中。输入初始值称为 segmentedSieve_Num，它为给定范围 [low, high] 创建一个布尔数组 isPrimeNum，并默认将所有索引设置为 true。

这样，simpleSieveNum 生成的素数用于确定每个素数在该范围内的第一个小倍数，并将 isPrimeNum 的倍数和后续值设置为 0。程序遍历 isPrimeNum 数组的另一个元素并打印出素数，并将其与 1 取反。程序通过向用户请求输入并调用分段筛法函数来结束，该函数确实对给定范围进行分段并确定该范围内的所有素数。

优点

当上限 R 可以达到数十亿时，分段筛法可以用于大范围的数字 [L, R]。它仍然是内存高效的，因为它不需要存储或处理直到 R 的数字。

• 降低空间复杂度： 与使用所有数字直到 R 的筛法相比，分段筛法只需要存储 L 和 R 之间的数字（包括 L 和 R），这节省了空间。
• 素数的重用： 埃拉托斯特尼筛法用于预先计算直到 Root R 的素数，为了标记范围 [L,R] 中的所有倍数，这些素数被重用。
• 分治法： 大数据输入也很容易管理，因为算法将问题分解为小部分。
• 可并行化： 由于不同的段可以相互独立地计算，因此该算法设计用于并行处理和多线程。
• 处理任意范围： 请注意，该算法能够识别 L 到 R 范围内的素数，几乎忘记了下限 L 总是 1。这种灵活性对于可能需要一定精度范围的问题非常重要。

缺点

分段筛法的几个缺点如下：

• 实现复杂： 与埃拉托斯特尼筛法相比，分段筛法由于其特殊情况和范围计算而更难编码。
• 初始开销： 计算直到 Root R 的素数涉及初始开销，这对于小范围或 R 相对较小的情况可能效率不高。
• 大范围的内存使用： 当计算直到 Root R 的素数时，肯定会有一些开销，这意味着它在小范围或 R 较小时使用最少。需要适当管理边缘结构和范围计算。
• 不适用于小范围： 对于较小的范围，生成直到 Root R 的素数的恒定成本可能与通过分段获得更简单方法所获得的收益适得其反。

结论

总之，分段筛法算法属于寻找素数的成本优化算法范围。分段筛法，尽管对于大范围优于简单筛法，但如果范围很广，特别是当 R 达到数十亿时，它将为 [L, R] 的布尔数组消耗大量内存。根据上述观察，它不需要一次存储所有素数，而只存储 L 和 R 之间的素数。这是通过使用称为埃拉托斯特尼筛法的筛法算法预先计算素数来完成的，该算法非常适合大数据集计算。如果将其分解为更具后续性的小问题，它也会更好地工作。

然而，它具有较高的难以理解性和初始成本，这使得它无法用于小范围和简单问题。分段筛法在需要在大区间生成素数并且速度和内存使用的微调满足要求的用途中是一种非常有效的方法。