经典素数筛算法学习笔记

素数筛算法是一种高效找出一定范围内所有素数的算法，主要应用于计算机科学和数学领域。在本篇笔记中，我们探讨了三种不同的素数筛选方法，分别是暴力枚举、线性筛（版本1）和线性筛（版本2与3）。下面我们将详细解释这些算法及其原理。

1. 暴力枚举法：这是最直观但效率最低的方法。对于每个数字i（从2开始），我们检查它是否能被2到sqrt(i)之间的任何数字整除。如果可以，那么i不是素数，否则是素数。这种方法的时间复杂度为O(N * logN)，空间复杂度为O(1)。尽管简单，但效率不高，不适合处理大规模数据。

2. 线性筛（版本1）：该方法利用了“素数过滤”的思想，即一旦找到一个素数p，就可以标记所有p的倍数为合数。这样做减少了重复计算，提高了效率。代码中，当找到素数时，不再检查其后的所有数字，而是跳过已知的合数。这种方法的时间复杂度为O(N)，空间复杂度为O(N)。

3. 线性筛（版本2与3）：进一步优化了线性筛（版本1），在存储素数时，不使用额外的变量cnt，而是直接将素数存入数组的前面。版本2与版本3的主要区别在于计数方式，版本2使用变量cnt，而版本3则使用数组的首个元素prime[0]作为计数器。这种方法同样具有O(N)的时间复杂度和O(N)的空间复杂度，但在空间利用上更加巧妙。素数筛算法的核心是利用素数的性质来减少不必要的计算，通过标记合数来避免对每个数字的重复检查。

在实际应用中，线性筛算法（版本2或3）通常是最优选择，因为它在保证效率的同时，尽可能地节省了内存空间。在编程实现时，需要注意以下几点：

• 初始化数组时，所有元素默认为非素数（通常是false或0）。
• 遍历过程中，首先检查当前数字是否已被标记为合数，如果是，则跳过。
• 当找到一个素数时，将其存入结果数组，并标记所有它的倍数为合数。
• 使用sqrt(i)作为上限可以减小检查范围，因为一个数如果不是素数，那么它的因子必然有一个小于等于它的平方根。

以上是素数筛算法的基本理解和实现，对于需要快速找出大量素数的情况，这种算法是不可或缺的工具。同时，它也为理解和研究更高级的数论问题提供了基础。