阶乘分解（素数筛选法&&分解质因子）
发布时间
阅读量：
阅读量
给定整数 N ，试把阶乘 N! 分解质因数，按照算术基本定理的形式输出分解结果中的 pi和 ci 即可。
输入格式
一个整数N。
输出格式
N! 分解质因数后的结果，共若干行，每行一对pi,ci，表示含有pici项。按照pi从小到大的顺序输出。
数据范围
1≤N≤106
输入样例：
5
输出样例：
2 3
3 1
5 1
样例解释
5!=120=23∗3∗5
思路：首先用素数筛选法得到1-n中所有的素数（即为：n！的所有质因子），然后对于其中每个质因子， 从n！中分解出质因子p乘积的形式（即：ps），其实s就是1~n这n个数是p的倍数的个数，显然，1~n这n个数中每有一个数是p的倍数，则p在n！中的幂次就多一个，所以只要求出**[n/p]+[n/p2]+[n/p^3]+...即为1~n这n个数是p的倍数的个数，即p在n！中出现的幂次** 。
int get_num(int p,int n)//得到质因子p在n!中的幂次（即：1-n这n个数中p的倍数的个数）
{
int s=0;
while(n) s+=n/p,n/=p;
return s;
}
完整代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e6+6;
int primes[maxn],cnt;
bool vis[maxn];
void get_primes(int n)
{
for(int i=2;i<=n;i++){
if(!vis[i]) primes[cnt++]=i;
for(int j=0;primes[j]*i<=n;j++){
vis[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}
int get_num(int p,int n)//得到质因子p在n!中的幂次（即：1-n这n个数中p的倍数的个数）
{
int s=0;
while(n) s+=n/p,n/=p;
return s;
}
int main()
{
int n;
cin>>n;
get_primes(n);
for(int i=0;i<cnt;i++){
int p=primes[i];
int num=get_num(p,n);
cout<<p<<" "<<num<<endl;
}
return 0;
}
全部评论 (0)
还没有任何评论哟~