小于 10^12 的质数之和

Question

如何求出所有小于 10^12 的素数之和？

我将埃拉托色尼筛法与 O(n * log(log(n))) 一起使用，但我想要一种算法来更快地计算它。

我的代码在 4 秒内运行 10^8，但计算 10^12 需要很多小时。

这是我的代码：

#include <iostream>
#include <vector>
#include <algorithm>

#define big  long long int
#define ubig unsigned long long  
#define SZ(x) int(x.size())
#define Pb push_back

using namespace std;

const big maxn = 1000 * 1000 + 10;
const big mod = 100000000;
const big Delta = 100000000;

bool s[mod], p[maxn]; 
big b[maxn]; 

vector <big> primes; 

ubig ans = 0, n;

void init_primes () {
    for (big i = 2; i <= 1000 * 1000; i++) {

        if (p[i]) continue;

        primes.Pb(i);

        b[SZ(primes)-1] = primes.back() * primes.back();

        for (big j = i * i; j <= 1000 * 1000; j += i) {
            p[j] = 1;
        }

    }
}

void sieve (big from, big to) {

    cerr << to / mod << " of " << n / mod  << "\n" ;

    fill (s,s+mod,0);

    for (big i = 0; i < SZ(primes) && primes[i] <= to; i++) {

        big j = b[i];

        for (; j <= to; j += primes[i]) {
            s[j%mod] = 1;
        }

        if (j >= b[i]) {
            b[i] = j;
        }

    }

    for (big k = 0; k < mod; k++) {
        if (s[k] == 0) {
            ans += from + k;
            // ans %= Delta;
        }
    }

}

int main () {

    init_primes();

    n = 1000ll * 1000 * 1000 * 1000;
    // cin >> n;

    for (big i = 0; i + mod <= n; i += mod) {
        sieve (i,i+mod);
    }

    cout << ans-1 << endl;
}

long long的溢出现在无所谓了！

Answer 1

我看到了两种明显的加速算法的方法。

首先，您使用 1000 * 1000 作为循环的限制。最好只计算一次：big limit = 1000 * 1000; 并在循环中使用变量 limit。根据您的编译器，您可能会在每次循环时重复乘法。

其次，您正在将 i-loop 步进 1。不要那样做。分别处理 i=2 的情况，然后从 i=3 循环，每次步进 2。这将使外循环的迭代次数减半。如需进一步节省，请查看 "Wheel factorization" 方法。

您可能想尝试将 p[] 设为位数组，而不是布尔数组以节省内存使用量。您的速度问题可能是由于内存过载和磁盘交换过多造成的。

小于 10^12 的质数之和

Sum of prime numbers below 10^12

c++

algorithm

primes

sum

sieve-of-eratosthenes