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

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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了《算法竞赛进阶指南》0x31质数 阶乘分解质因数，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1162字，纯文字阅读大概需要2分钟。

内容图文

题目链接：https://www.acwing.com/problem/content/199/

分解N！的质因数，因为N!的质因数不超过N，所以可以先预处理出[1,N]的质数，然后就是简单的求和计算了。

筛法采用的是优化之后的艾式筛法的优化了，算法的时间复杂度是O(n*loglogn)，十分接近线性。

代码： 

#include<iostream>
#include<vector>
#include<cstring> 
usingnamespace 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>
usingnamespace 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

内容总结

以上是互联网集市为您收集整理的《算法竞赛进阶指南》0x31质数 阶乘分解质因数全部内容，希望文章能够帮你解决《算法竞赛进阶指南》0x31质数 阶乘分解质因数所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1185446.html

来源：【匿名】