埃拉托色尼筛的优化

Question

我目前正在尝试进一步优化我的筛子。我必须使用 eratosthenes 筛法计算两个数字之间的素数，我知道需要工作的两个数字是 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

您可能运行内存不足。使用 bool 数组可能会为每个条目分配 1 个字节，如果您允许使用 std::vector，则 std::vector<bool> 仅使用一个位。

Answer 2

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

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

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

Answer 3

2000000000000 这对于数组来说太大了。而是使用位集。您可以更快地生成更大的素数。以这种方式在全局范围内声明位集，它可以容纳 10^7。但随后您可以使用分段筛算法使其适用于 2000000000000。在这种情况下 sqrt(2000000000000) = 1414213.something 这就是为什么您必须生成 2 到 1414214 之间的所有素数的原因。然后使用分段筛算法

#include <bits/stdc++.h>
#define bitset_range 1414214
typedef long long int lli;
typedef long int li;
using namespace std;
template <typename T>
void printer(T a) {
    cout << a << endl;
}
vector<li> stock_prime;
bitset<bitset_range + 1> numbers;
int main() {
    lli start, stop;
    //normal seieve
    numbers.set();
    numbers.reset(0);
    numbers.reset(1);
    for (li i = 2; i <= bitset_range; i++) {
        if (numbers.test(i)) {
            for (li j = i * i; j <= bitset_range; j+= i) {
                numbers.reset(j);
            }
            stock_prime.push_back(i);
        }
    }
    //for_each(stock_prime.begin(), stock_prime.end(), printer<int>);
    cout << "Size: " << stock_prime.size() << endl;

    //now use segmented seive algorithm here remember to use bitset rather than bool array



    return 0;
}

埃拉托色尼筛的优化

Optimizing Sieve of Eratosthenes

c++

algorithm

optimization

sieve-of-eratosthenes