【每日一题】Forsaken喜欢数论

题目

对于任意一个数 ，会返回 的最小质因子。如果这个数没有最小质因子，那么就返回 0。
现在给定任意一个 ，求 的值。

解题思路

在从 1 到 遍历整数时，使用筛法求素数。
如果本身是素数，那么它本身就是它的最小质因子，累加计入 。
遍历由该素数生成的合数，如果还没访问过，表示这个合数的最小质因子就是该素数，累加计入 。

C++代码

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<bool> vis(n+1, false);
    long long ans = 0;
    for(long long i=2; i<=n; ++i){
        if(!vis[i]){
            ans += i;
            for(long long j=i*i; j<=n; j+=i){
                if(!vis[j]){
                    vis[j] = true;
                    ans += i;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}