解题思路

求每一个数的最小质因子，想到了雨巨讲的线性筛。
借这个题存一下线性筛模板

int v[maxn]; //存放每个数的最小质因子
int prime[maxn]; //存放素数
int cnt; //素数个数
for(int i=2;i<=n;i++){
        if(v[i]==0){
            v[i]=i; prime[++cnt]=i; //如果这个数没有被访问过，则为素数，存下来
        }
        for(int j=1;j<=cnt;j++){  //遍历已经存的素数，将其作为最小质因子筛去合数
            if(prime[j]>v[i]||i*prime[j]>n) break;
            v[i*prime[j]]=prime[j];
        }
    }

埃氏筛每个合数可能会被筛多次，而线性筛每个合数只会被其最小质因子筛一次，从而使复杂度降为O(n)

AC代码

#include <bits/stdc++.h>
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define maxn 30000010
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int MOD=1000000007;
const double pi=acos(-1.0);
inline int lowbit(int x){ return x&(-x);}
int v[maxn];
int prime[maxn];
int cnt;
int main()
{
    io;
    int n;
    cin>>n;
    ll ans=0;
    for(int i=2;i<=n;i++){
        if(v[i]==0){
            v[i]=i; prime[++cnt]=i;
        }
        for(int j=1;j<=cnt;j++){
            if(prime[j]>v[i]||i*prime[j]>n) break;
            v[i*prime[j]]=prime[j];
        }
    }
    for(int i=2;i<=n;i++) ans+=v[i];
    cout<<ans<<endl;
    return 0;
}