题解 | Forsaken喜欢数论

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

int main(){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    long long n,sum=0,i=2,j;
    cin>>n;
    vector<bool> a(n+1,true);
    for(;i<=n;i++){
        if(a[i]){                            //判断是否是素数
            a[i]=false;
            sum+=i;
            for(j=i*i;j<=n;j+=i){
                if(a[j]){                    //防止重复加
                    sum+=i;
                    a[j]=false;              //标记不是素数
                }
            }
        }
    }
    cout<<sum<<endl;
}

这其实就是素数筛的一个变式，我用的是埃氏筛，初始化2~n所有数都为素数，然后遍历一个素数，那它所有倍数的最小质因数就都是这个数，2~n中有多少个它的倍数，总和就加多少个这个数，再把所有它的倍数都标记为不是素数就行了，记得筛选一下，防止重复加。