牛客题解-Forsaken喜欢数论

链接：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=1n​f(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; }