题目链接：https://www.acwing.com/problem/content/199/
分解N！的质因数，因为N!的质因数不超过N，所以可以先预处理出[1,N]的质数，然后就是简单的求和计算了。
筛法采用的是优化之后的艾式筛法的优化了，算法的时间复杂度是O(n*loglogn)，十分接近线性。
代码：
#include<iostream> #include<vector> #include<cstring> using namespace std; #define maxn 1000010 vector<int>primes; bool v[maxn]; void get_primes(int n){ memset(v,0,sizeof(v)); for(int i=2;i<=n;i++){ if(v[i])continue; primes.push_back(i); for(int j=i;j<=n/i;j++)v[i*j]=1; } } int main(){ int n; cin>>n; get_primes(n); for(int i=0;i<primes.size();i++){ int p=primes[i]; int s=n,c=0; while(s)c+=s/p,s/=p; printf("%d %d\n",p,c); } }
质数的线性时间筛法：（采用的是最小质因数筛法，因为每个合数一定有一个唯一的最小质因数）
#include<iostream> using namespace std; #include<cstring> #define maxn 1000 int v[maxn+10],prime[maxn+10]; int main(){ int m=0; for(int i=2;i<=maxn;i++){ if(!v[i]){ v[i]=i;prime[++m]=i; } for(int j=1;j<=m;j++){ if(prime[j]>v[i] || i*prime[j]>maxn)break; v[i*prime[j]]=prime[j]; } } for(int i=1;i<=m;i++){ if((i-1)%10 == 0 && i!=1)cout<<endl; cout<<prime[i]<<" "; } }
原文：https://www.cnblogs.com/randy-lo/p/13177404.html