1 条题解
-
0
【本题解由站长编写】
埃氏筛求 n 以内所有素数之和。n 最大 200 万,标记数组开 n+1。遍历 i 从 2 到 n,若 i 未被标记则为素数、累加进和,并把 i 的倍数(从 i*i 起)标记掉。求和用 long long——200 万以内的素数之和约 1.4×10^11,超出 int。
代码(C++17)
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<char> isComposite(n + 1, 0); long long sum = 0; for (int i = 2; i <= n; i++) { if (isComposite[i]) continue; sum += i; for (long long j = (long long)i * i; j <= n; j += i) isComposite[j] = 1; } cout << sum << endl; return 0; }
- 1
信息
- ID
- 4209
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者