链接：https://ac.nowcoder.com/acm/contest/127889/A
来源：牛客网
题目描述
Forsaken有一个有趣的数论函数。对于任意一个数xxx，f(x)f(x)f(x)会返回xxx的最小质因子。如果这个数没有最小质因子，那么就返回0。
现在给定任意一个nnn，Forsaken想知道∑i=1nf(i)\sum_{i = 1}^{n}{f(i)}∑i=1nf(i)的值。
输入描述:
一个整数nnn。
输出描述:
一个整数代表上面的求和式的值。
示例1
输入
复制4
4
输出
复制7
7
备注:
1≤n≤3e71 \leq n \leq 3e71≤n≤3e7
筛法预处理最小质因子
可以用埃氏筛的变种预处理每个数的最小质因子（SPF，Smallest Prime Factor），再累加结果。时间复杂度优化为O(n log log n)，能高效处理3e7规模的输入。
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll a; cin >> a; if (a < 2) { cout << 0 << endl; return 0; } vector<ll> spf(a + 1); for (ll i = 2; i <= a; ++i) { if (spf[i] == 0) { spf[i] = i; for (ll j = i * 2; j <= a; j += i) { if (spf[j] == 0) { spf[j] = i; } } } } ll sum = 0; for (ll i = 1; i <= a; ++i) { if (i == 1) { sum += 0; } else { sum += spf[i]; } } cout << sum; return 0; }
