C++版埃拉托斯特尼筛法

旨在识别指定范围内或 up to specified limit 'n' 的所有素数。它以古希腊数学家 Eratosthenes 的名字命名。该算法提供了一种系统的方法来筛除非素数，使其成为数论和各种计算应用中宝贵的工具。

该算法首先创建一个从 2 到 'n' 的数字列表，并最初假设它们都是素数。然后，它系统地标记每个素数的倍数，从最小的素数 2 开始。随着算法的进展，它会逐步发现给定范围内的素数。

驱动 埃拉托斯特尼筛法 的关键见解是任何素数的倍数本身都是 合数（非素数）。因此，该算法通过连续标记这些倍数来有效地过滤掉非素数候选。该过程一直持续到达到 'n' 的平方根，之后剩余的未标记数字被确认为素数。

初始化：创建一个大小为 'n+1' 的布尔数组或向量，其中每个元素代表从 0 到 'n' 的一个数字。最初，所有元素都设置为 “true”，以假定所有数字都是素数。

标记非素数：从第一个素数 2 开始。通过将 2 的所有倍数对应的数组元素设置为 “false” 来将其标记为非素数。此步骤从潜在素数列表中消除了 4, 6, 8, 10 等数字。

查找下一个未标记的数字：标记完 2 的倍数后，找到大于 2 的下一个 未标记的数字。这个数字将是下一个素数。在第一次迭代中，它是 3。

重复过程：继续通过将下一个素数（在此情况下为 3）的所有倍数标记为 非素数 来重复该过程。在下一次迭代中，找到下一个未标记的数字，它将是下一个素数（在此情况下为 5），然后重复该过程。一直重复此迭代，直到达到 'n' 的平方根。

结果：过程完成后，数组中所有 未标记的数字 都是素数。该算法已经筛除了非素数，只剩下素数。

埃拉托斯特尼筛法在查找素数方面效率很高，尤其是在处理大范围数字时，因为它避免了对每个数字单独进行昂贵的素数测试操作。相反，它系统地消除了已知素数的倍数来识别新的素数。

程序 1

这是 埃拉托斯特尼筛法 算法的 C++ 代码实现，用于查找给定限制 'n' 之内的所有素数。此代码使用基本方法，带有布尔向量来标记素数和非素数。

输出

Enter the limit (n): 20
Prime numbers up to 20 are: 2, 3, 5, 7, 11, 13, 17, 19

说明

• 程序以包含必要的库开始：用于输入/输出的 iostream 和用于使用动态数组存储素数的 vector。
• 定义了 sieveOfEratosthenes 函数来实现埃拉托斯特尼筛法算法。它接受一个 整数 n 作为输入，表示查找素数的上限。

在 sieveOfEratosthenes 函数内部

• 创建了一个大小为 n + 1 的布尔向量 isPrime。此向量的每个元素代表一个从 0 到 n 的数字。最初，所有元素都设置为 true，假定所有数字都是素数。
• isPrime 向量中索引 0 和 1 处的元素被显式设置为 false，因为 0 和 1 不是素数。
• 算法的主要部分从一个 for 循环 开始，该循环从 2 迭代到 n 的平方根 (p * p <= n)。此循环负责查找素数。

在循环内

• 如果 isPrime[p] 为 true，则表示 p 是一个素数。
• 之后，我们进入另一个循环，该循环从 p * p 开始，并以 p 为步长递增。此内循环通过将 isPrime 向量中相应的元素设置为 false 来将 p 的所有倍数标记为非素数。它消除了已知 素数 的倍数的数字。
• 外循环完成后，isPrime 向量包含素数的 true 值和非素数的 false 值。
• 最后，代码以人类可读的格式打印出 up to n 的素数。使用一个 first 变量来处理输出的格式（在素数之间添加逗号）。

在主函数中

• 提示用户输入用于查找素数的 限制 (n)。
• 如果 n 小于 2，则显示一条消息，表明在指定范围内没有素数。
• 否则，将调用 sieveOfEratosthenes 函数来查找并打印 up to n 的素数。

复杂度分析

时间复杂度

外循环：sieveOfEratosthenes 函数中的外循环从 2 迭代到 'n' 的平方根。在 Big O 符号中，这部分的时间复杂度为 O(sqrt(n))。这是因为我们只需要考虑 up to 'n' 的平方根的素数即可消除倍数。

内循环：在外循环内部，有一个内循环将当前素数 'p' 的倍数标记为非素数。内循环对每个素数 'p' 大约运行 'n/p' 次。随着我们的进展，'p' 变大，它标记的倍数数量减少。因此，所有素数的迭代总和大致为

n/2 + n/3 + n/4 + ... + n/p

该级数收敛到 n * (1/2 + 1/3 + 1/4 + ... + 1/p)，在最坏情况下约等于 n * log(log(n))。

总时间复杂度：将外循环和内循环的时间复杂度结合起来，埃拉托斯特尼筛法的总体时间复杂度约为 O(sqrt(n) * log(log(n)))。

空间复杂度

埃拉托斯特尼筛法的空间复杂度由存储布尔向量 isPrime 所需的空间决定，该向量包含 'n + 1' 个元素。

因此，该算法的空间复杂度为 O(n)。

程序 2

在 C++ 中实现埃拉托斯特尼筛法算法的另一种方法是使用一种更节省内存且空间需求更少的方法。此方法使用 bitset 而不是布尔向量来减少内存使用。以下是使用此方法的 C++ 实现。

输出

Enter the limit (n): 50
Prime numbers up to 50 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

说明

• 程序以包含必要的库开始：用于输入/输出操作的 iostream，用于高效存储素数信息的 bitset，以及用于数学函数的 cmath。
• 定义了 sieveOfEratosthenes 函数来实现埃拉托斯特尼筛法算法。它接受一个整数 n 作为输入，表示查找素数的上限。

在 sieveOfEratosthenes 函数内部

• 有一个检查用于处理 'n' 小于 2 的特殊情况。如果 'n' 小于 2，则表示指定范围内没有素数，因此会显示一条消息，并且函数会提前返回。
• 创建了一个大小为 1000001 的 bitset，名为 isPrime。此 bitset 用于高效地将数字标记为素数（1）或非素数（0）。它提供了布尔向量的内存高效替代方案。
• isPrime bitset 中的所有数字都初始化为素数（设置为 1），因为我们从假设所有数字都是素数开始。之后我们会将非素数标记为 0。
• 数字 0 和 1 被显式标记为非素数（设置为 0），因为它们不是素数。
• 之后，算法从第一个素数 2 开始，继续标记非素数。
• 埃拉托斯特尼筛法算法的核心是 for 循环 中的部分：
• 外循环从 2 迭代到 'n' 的平方根 (p * p <= n)。此循环负责查找素数。

在循环内

• 如果 isPrime[p] 为 true，则表示 'p' 是一个素数。
• 内循环从 p * p 开始，并以 'p' 为步长递增。它通过将 bitset 中相应的位设置为 0 来将 'p' 的所有倍数标记为非素数。它消除了已知 素数 的倍数的数字。
• 外循环完成后，bitset isPrime 包含素数的 1 和非素数的 0。
• 最后，代码以人类可读的格式打印出 up to 'n' 的素数。使用一个 first 变量来处理输出的格式（在素数之间添加逗号）。

在主函数中

• 提示用户输入用于查找素数的 限制 (n)。
• 调用 sieveOfEratosthenes 函数来查找并打印 up to 'n' 的素数。
• 此实现由于使用了 bitset 而具有内存效率，并且保留了约 O(sqrt(n) * log(log(n))) 的时间复杂度，使其适用于在给定范围内查找素数。

复杂度分析

时间复杂度

初始化阶段涉及设置一个大小为 1000001 的 bitset，代表从 0 到 'n' 的数字。此初始化步骤需要 O(n) 时间，但由于 bitset 的固定大小，在实际应用中可以视为常量。

算法的核心是外循环，负责素数检测。它迭代约 sqrt(n) 次 (O(sqrt(n))) 来识别素数。这是因为在查找素数时，无需考虑大于 'n' 平方根的数字。

内循环将素数的倍数标记为 非素数，并且总共运行约 n * log(log(n)) 次。此复杂度源于素数被发现时迭代次数的减少，在最坏情况下收敛到 n * log(log(n))。

总时间复杂度可表示为 O(n + sqrt(n) + n * log(log(n)))，包括初始化、素数检测和标记倍数。实际上，内循环的贡献 n * log(log(n)) 占主导地位。这种详细的分解阐明了时间如何在各种算法步骤中分配，从而有助于对其效率进行全面理解。

空间复杂度

用于素数标记的 Bitset

• 名为 isPrime 的 bitset 用于将数字标记为素数（1）或非素数（0）。
• bitset 的大小固定为 1000001，足以处理 up to 'n' 的数字。
• 因此，bitset 的空间复杂度为 O(1000001)，可以近似为 O(1)，因为它是固定大小的数据结构。

附加空间

代码中还使用了一些附加变量，例如整数变量（n, p, i, first 等），它们占用固定量的内存。

因此，这些变量的空间复杂度为 O(1)。