【欧拉计划第 10 题】 质数之和 Summation of primes

发表于 分类于 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 1 分钟

Problem 10 Summation of primes

The sum of the primes below $10$ is

$$
\large 2 + 3 + 5 + 7 = 17
$$

Find the sum of all the primes below two million.

问题 10 质数之和

$10$ 以下的质数之和为

$$
\large 2 + 3 + 5 + 7 = 17
$$

求两百万以下的所有质数之和

思路分析

首先单看题目知识点，涉及到素数（质数），和第七题 10001st prime一定会有类似之处

我们采用最直接的方法求解（暴力），枚举范围内的所有质数，然后求和

注意，像这样的解决方案并非最佳，只适用于小规模数据，规模的调整对于对应算法的要求很高

比如说，这个题目你可以用暴力枚举解决它。但是，如果我把数据量级调整到亿，这种方法就未必可以使用，需要更高级的算法来解决，具体请参考文末代码段

总之，大家要根据实际情况采用最优的方案来解决对应的问题，没有什么办法可以一劳永逸，适用于所有情况

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*
 * @Author: coder-jason
 * @Date: 2022-04-17 15:33:41
 * @LastEditTime: 2022-04-17 16:04:24
 */
#include <bits/stdc++.h>
using namespace std;

long long sum = 0; // 注意数据范围,考虑溢出情况

bool is_prime(int num)
{
    for (int i = 2; i <= sqrt(num); i++)
        if (num % i == 0)
            return false;
    return true;
}

int main()
{
    for (int i = 2; i < 2000000; i++)
        if (is_prime(i))
            sum += i;
    cout << sum << endl;
    return 0;
}

答案：142913828922

埃拉托斯特尼筛

原理：从 $2$ 开始，将每个素数的各个倍数，标记成合数。一个素数的各个倍数，是一个差为此素数本身的等差数列，此筛法是列出所有小素数最有效的方法之一

这里使用埃氏筛法解决亿级数据量级问题，实现代码段如下，供参考学习

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
 * @Author: coder-jason
 * @Date: 2022-04-17 15:33:41
 * @LastEditTime: 2022-04-17 20:33:01
 */
#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\n", sieve(1000000000));
    return 0;
}

更多关于本题的解决方案，详见 求十亿内所有质数的和，怎么做最快?