题解 | #Forsaken喜欢数论#

这题其实就是把每个数的最小质因子都快速找出来再累加，1 的最小质因子按题意算 0，所以不用加。
直接用线性筛：一边筛素数，一边给每个合数打上“第一个质因子”标签，这样每个数都只会被处理常数次，整体是 O(n)。
最后把 2 到 n 的最小质因子加起来就是答案。

void solve(){
    int n;cin>>n;
    vi p;
    p.reserve(2000000);
    vector<int> lp(n+1,0);
    ll ans=0;
    for(int i=2;i<=n;++i){
        if(lp[i]==0){
            lp[i]=i;
            p.push_back(i);
        }
        ans+=lp[i];
        for(int j=0;j<(int)p.size();++j){
            ll x=1LL*i*p[j];
            if(x>n)break;
            lp[(int)x]=p[j];
            if(p[j]==lp[i])break;
        }
    }
    cout<<ans<<endl;
}