题目
题目描述
Forsaken有一个有趣的数论函数。对于任意一个数 \(x\) ， \(f(x)\) 会返回 \(x\) 的最小质因子。如果这个数没有最小质因子，那么就返回0。
现在给定任意一个 \(n\) ，Forsaken想知道 \(\sum_{i = 1}^{n}{f(i)}\) 的值。
输入描述
一个整数 \(n\) 。
输出描述
一个整数代表上面的求和式的值。
示例1
输入
4
输出
7
备注
\(1 \leq n \leq 3e7\)
题解
知识点：筛法。
线性筛本身即是用最小质因子筛质数，因此只需要在中间记录最小质因子即可。
这种性质可以使得我们可以线性求出积性函数的值。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e7 + 7;
bool vis[N];
vector<int> prime;
int f[N];
void get_prime(int n) {
f[1] = 0;
for (int i = 2;i <= n;i++) {
if (!vis[i]) prime.push_back(i), f[i] = i;
for (auto j : prime) {
if (i * j > n) break;
vis[i * j] = 1;
f[i * j] = j;
if (!(i % j)) break;
}
}
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
get_prime(n);
ll ans = 0;
for (int i = 1;i <= n;i++) ans += f[i];
cout << ans << '\n';
return 0;
}