用C++实现一个高效的素数筛选算法

一、素数筛选算法介绍

素数指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。因此，素数筛法指的是，通过筛选的方式找出指定范围内的素数。

常见的素数筛法有：Erastothenes筛、Sundaram筛、Euler筛、Atkin筛等。其中，Erastothenes筛是最常用、最简单的筛法，其基本思想是：先假设范围内所有数都是素数，然后从小到大循环，将每个素数的倍数都标记为合数，最后剩下的即为素数。

二、Erastothenes筛的实现

Erastothenes筛的具体实现如下：

#include 
#include 
   
#include 
    
using namespace std;

int main(int argc, char** argv) {
    int MAXN = 1000000;
    bool* isPrime = new bool[MAXN + 1];
    memset(isPrime, true, MAXN + 1);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= MAXN; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j <= MAXN; j += i) {
                isPrime[j] = false;
            }
        }
    }
    for (int i = 1; i <= MAXN; ++i) {
        if (isPrime[i]) {
            cout << i << endl;
        }
    }
    delete[] isPrime;
    return 0;
}

    
   
  

上述代码中，我们首先定义了一个大于等于2的自然数范围MAXN（一般为10^6左右），然后创建一个bool类型的数组isPrime，其中isPrime[i]=true代表i是素数，isPrime[i]=false代表i是合数。

接着，我们将isPrime数组内所有元素初始化为true，然后将isPrime[0]和isPrime[1]置为false，因为0和1都不是素数。

最后，我们循环遍历从2到MAXN的每一个数字i，如果isPrime[i]=true，说明i是一个素数，因此我们需要将i的倍数（包括i本身）都标记为合数。为了提高效率，我们从i的平方数开始，按照i的倍数逐个标记。由于i的2倍~i*(i-1)倍已经在之前的循环中被标记为合数了，因此我们从i的i倍开始标记，即i的平方。

最后，我们再次循环遍历isPrime数组，将isPrime[i]=true的元素输出即可。

三、算法时间复杂度和优化

上述算法的时间复杂度为O(n*log(log(n)))，因为每一个合数都会进行一次标记，每个素数的倍数都会被标记，每个素数的标记次数不超过log(log(n))次。当n达到10^9时，程序运行时间已经可以达到数分钟，因此我们需要对该算法进行优化。

一种优化方法是使用bitset代替bool数组。由于bool类型占用一个字节，而bitset可以按位存储，因此使用bitset可以极大地减少内存占用。

另一种优化方法是对标记过程进行优化。我们发现，对于每一个素数，其小于i的倍数已经都被标记过了，因此在标记i的倍数时，可以从i的2倍开始，这样可以避免重复标记。

对上述两种优化进行结合，可以使Erastothenes筛法的速度大大提升。

四、总结

Erastothenes筛法是一种简单、高效的素数筛选算法，其基本思想是从小到大筛选素数。通过将合数标记为 false，最后剩下的即为素数，因此该算法的效率取决于标记合数的快慢。

为了提高程序效率，我们可以使用bitset代替bool数组，以及优化标记过程以避免重复标记。这些优化措施能够显著地提高程序运行速度，让我们能够在较短的时间内求解出较大范围内的素数。