题目链接：点此跳转
题目大意：求出1到n每个数的最小质因子的和，f(i)没有质因子的话为0；
解题思路：1到n的最小质因子和，我们可以联想到素数筛（欧拉筛/质数筛），只需要在筛法筛素数的时候维护每个数的最小质因子即可，即bool函数 vis 记录最小质数，初始化后，从1到n累加一次即可
Code：
#include<iostream> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N=3e7+5; int prime[N],f[N]; int cnt; void init(){ //素数筛 for(int i=2;i<N;i++){ if(!f[i]) prime[cnt++]=i,f[i]=i; for(int j=0;prime[j]<=N/i;j++){ f[prime[j]*i]=prime[j]; //f记录最小质因子 ， 素数质因子为0 if(i%prime[j]==0) break; } } } int main(){ int n; init(); scanf("%d",&n); ll ans=0; for(int i=1;i<=n;i++) ans+=f[i]; printf("%lld\n",ans); return 0; }