题意:求出1-n所有数的最小质因子之和。
题记:筛质数的模板题。用每一个数的最小质因子取筛掉这个数,同时把这个质数加到答案中。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e7+10; bool st[N]; int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int n; cin>>n; ll sum=0; for(int i=2;i<=n;i++){ if(st[i]) continue; sum+=i; for(int j=i+i;j<=n;j+=i){ if(!st[j]){ st[j]=true; sum+=i; } } } cout<<sum<<endl; return 0; }