【每日一题】6月23日Forsaken喜欢数论 线性筛
Forsaken喜欢数论
https://ac.nowcoder.com/acm/problem/53079
解题思路
求每一个数的最小质因子,想到了雨巨讲的线性筛。
借这个题存一下线性筛模板
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; }