求十亿内所有质数的和

方法一：动态规划

详情见 知乎——求十亿内所有质数和，怎么做最快？.

以下代码只是其中Python版的翻版

时间复杂度约为 $O(n^frac{3}{4})$，但在我辣鸡电脑上用了4s

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 2e5+10;
int V[maxn];
map<int, ll>S;

ll Sum(ll n)
{
    int m = (int)sqrt(n);
    int t = n / m;
    for(int i = 1;i <= m;i++)  V[i-1] = n / i;

    int cnt = 1;
    for(int i = t + m - 2;i >= m;i--)  V[i] = cnt++;


    for(int i = 0;i <= t+m-2;i++)  S[V[i]] = 1LL * V[i] * (V[i]+1) / 2 - 1;

    for(int p = 2;p <= m;p++)
    {
        if(S[p] > S[p-1])
        {
            ll sp = S[p-1];
            ll p2 = p *  p;
            for(int i = 0;i <= t+m-2;i++)
            {
                ll v = V[i];
                if(v < p2)  break;
                S[v] -= p*(S[v/p] - sp);
            }
        }
    }

    return S[n];
}

int main()
{
    printf("%lld
", Sum(1000000000));
}

方法二：埃氏筛法

思路很简单，筛出所有的质数再相加。

时间复杂度为 $O(nloglogn)$，在我电脑上用时23s.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 1e9 + 10;
bool vis[maxn];

ll sieve(int n)
{
    ll ret = 0;
    int m = (int)sqrt(n + 0.5);
    for (int i = 2; i <= m; i++) if(!vis[i])
    {
        for (int j = i * i; j <= n; j += i)  vis[j] = true;
        ret += i;
    }
    for(int i = m+1;i <= n;i++)  if(!vis[i])
        ret += i;
    return ret;
}

int main()
{
    printf("%lld
", sieve(1000000000));
    return 0;
}