题解 | #Forsaken喜欢数论#

该问题的核心是求 到 范围内每个正整数的最小质因子（Smallest Prime Factor, SPF）之和。

算法：线性筛法 (Linear Sieve / Euler Sieve)

由于 的定义直接指向数论中的“最小质因子”，线性筛法（欧拉筛）是解决此问题的最理想工具。

1. 为什么选择线性筛？

传统的埃拉托斯特尼筛法（Sieve of Eratosthenes）在标记合数时，一个合数可能会被其多个质因子重复更新（例如 12 会被 2 和 3 同时更新）。其时间复杂度为 。

而线性筛的核心逻辑是：每个合数只会被其最小质因子筛选一次。这与题目要求的 完美契合。在线性筛执行过程中，当我们需要标记 为合数时， 恰恰就是这个新生成的合数的最小质因子。

2. 数论属性应用

• 如果 是质数，。
• 在筛法遍历过程中，对于正在处理的数 和已找到的质数列表 ，新生成的合数 的最小质因子：
  • 由于线性筛保证了从最小的质数开始尝试，且在满足 时及时中断，因此 始终是 的最小质因子。即 。

复杂度分析

• 时间复杂度：。每个数仅被访问一次，且每个合数仅由其最小质因子标记。
• 空间复杂度：。需要一个布尔数组 is_prime（或 min_prime 数组）来记录状态，以及一个动态或静态数组存储已发现的质数。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    cin >> n;
    vector<bool> vis(n + 1, false);
    vector<ll> primes;
    ll S = 0;

    for (ll i = 2; i <= n; i++) {
        if (!vis[i]) {
            primes.push_back(i);
            S += i;
        }
        
        for (ll P : primes) {
            ll M = i * P;
            if (M > n)
                break;
            vis[M] = true;
            S += P;
            if (i % P == 0)
                break;
        }

    }

    cout << S << endl;
}