题目描述
给定整数 N ,试把阶乘 N! 分解质因数,按照算术基本定理的形式输出分解结果中的 pi 和 ci 即可。
输入格式
一个整数N。
输出格式
N! 分解质因数后的结果,共若干行,每行一对pi,ci,表示含有pcii项。按照pi从小到大的顺序输出。
数据范围
1≤N≤106
样例
输入样例:
5
输出样例:
2 3
3 1
5 1
样例解释
5!=120=(2^3)∗3∗5
用线性筛筛出n以内的质数,再求每个质数在n中的指数
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1000010;
int primes[N],cnt;
bool st[N];
void get_primes(int n){
for(int i=2;i<=n;i++){
if(!st[i])primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++){
st[primes[j]*i]=true;
if(i%primes[j]==0)break;//找到了i的最小质因子
}
}
}
int main(){
int n;
cin>>n;
get_primes(n);//1~n用线性筛筛出质数
for(int i=0;i<cnt;i++){
int p=primes[i];//枚举1~n中的每个质数
int s=0,t=n;//s表示当前质数在n中的个数
while(t)s+=t/p,t/=p;//p,p^2,p^3,……,一层一层筛,直到t/p等于0为止(即n不包含p^k,所有的p都找全了)
cout<<p<<" "<<s<<endl;
}
return 0;
}