题解 | Forsaken喜欢数论

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

const ll N = 3e7; // 质数筛选最大范围
vector<ll> primes;         // 存储筛出的所有质数
vector<bool> is_prime(N + 1, true); // 标记是否为质数，初始默认是质数


int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    ll n;
    cin >> n;



    ll sum = 0; // 总和必须用long long，避免int溢出

    is_prime[0] = is_prime[1] = false; // 0和1不是质数
    for (ll i = 2; i <= n; ++i) {   // 遍历2~MAXN所有数
        if (is_prime[i]) {
            primes.push_back(i);       // 未被标记则是质数，加入数组
            sum += i;
        }
        for (ll p : primes) {          // 用已筛质数标记合数
            if (i * p > n) break;   // 超出范围则终止
            sum += p;
            is_prime[i * p] = false;   // 标记i*p为合数
            if (i % p == 0) break;     // 本句为线性筛核心，保证仅被最小质因子标记
        }
    }

    cout << sum << '\n';
    return 0;
}