Problem 10 Summation of primes
The sum of the primes below 10 1010 is
2 + 3 + 5 + 7 = 17 \large 2 + 3 + 5 + 7 = 172+3+5+7=17
Find the sum of all the primes below two million.
问题 10 质数之和
10 1010 以下的质数之和为
2 + 3 + 5 + 7 = 17 \large 2 + 3 + 5 + 7 = 172+3+5+7=17
求两百万以下的所有质数之和
思路分析
首先单看题目知识点，涉及到素数（质数），和第七题 10001st prime一定会有类似之处
我们采用最直接的方法求解（暴力），枚举范围内的所有质数，然后求和
注意，像这样的解决方案并非最佳，只适用于小规模数据，规模的调整对于对应算法的要求很高
比如说，这个题目你可以用暴力枚举解决它。但是，如果我把数据量级调整到亿，这种方法就未必可以使用，需要更高级的算法来解决，具体请参考文末代码段
总之，大家要根据实际情况采用最优的方案来解决对应的问题，没有什么办法可以一劳永逸，适用于所有情况
代码实现
/* * @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 22 开始，将每个素数的各个倍数，标记成合数。一个素数的各个倍数，是一个差为此素数本身的等差数列，此筛法是列出所有小素数最有效的方法之一
这里使用埃氏筛法解决亿级数据量级问题，实现代码段如下，供参考学习
/* * @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; }
