c++ - 埃拉托色尼筛的优化

Question

我目前正在尝试进一步优化我的筛子。我必须使用埃拉托色尼筛法计算两个数字之间的素数，我知道需要工作的两个数字是 2000000000000 和 2000000100000。由于运行时间过长，我当前的代码出现段错误。任何优化方面的帮助将不胜感激:

#include <iostream>
#include <cmath>
using namespace std;

double Sieve(long long a, long long b){

    //Create array of type bool
    bool *prime;
    prime = new bool[b];

    //Set all values in array to true
    for (long i = 0; i < b; i++){
        prime[i] = true;
    }


    long count = 0;

    //Runs through main Sieve algorithm
    for (long x = 2*2; x <= (b); x += 2 ){
        prime[x] = false;
    }
    for (long x = 3; x <= sqrt(b); x = 2*x ){
        if (prime[x] == true){
            for (long y = pow(x,2); y <= b; y += x){
                prime[y] = false;
            }
        }

    }

    //Loop to print out and count how many primes are present
    for (long x = a; x <= b; x++){
        if(prime[x] == true){
            count++;
        }
    }
    return count;
}

int main(){
    int a, b;
    cout << "Please enter two numbers separated by one space" << endl;
    cin >> a >> b;
    cout << Sieve(1,20) << endl;
    cout << Sieve(a,b) << endl;
}

Answer 1

您正在尝试分配方式 过多的内存，并且 new可能失败并抛出 std::bad_alloc exception .如果您不注意，未捕获的异常可能类似于段错误。

要解决此问题，您需要两个 数组 - 一个用于大小为 100001 的输出范围，另一个用于确定 sqrt(b) 以内的素数。

如另一个答案所述，使用 std::vector<bool>还将减少 8 倍的内存需求。这不足以消除需要两个数组的需求，但仍然有很大帮助。有时人们会反对vector<bool>因为它有一些奇怪之处，但就此而言它是完美的。