跳至正文

1 条题解

  • 0
    @ 2026-10-8 18:53:36

    【本题解由站长编写】

    埃氏筛求 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
    上传者