《算法竞赛进阶指南》0x31质数 阶乘分解质因数

题目链接：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
",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]<<" ";
    }
}