题目描述
给定整数 N ,试把阶乘 N! 分解质因数,按照算术基本定理的形式输出分解结果中的 pi 和 ci 即可。
输入格式
一个整数N。
输出格式
N! 分解质因数后的结果,共若干行,每行一对pi,ci,表示含有pcii项。按照pi从小到大的顺序输出。
数据范围
1≤N≤106
输入样例
5
输出样例
2 3
3 1
5 1
思路
首先使用埃及筛筛选出从1-n中是素数的数,如果不是素数则标记为1,并将其存入素数数组
对于每一个素数,计算在1-n中这个素数的个数
n! = 1 * 2 * 3 * ... * n
例如n=5
在1-n中的质数有2,3,5
当质数为2时,计算有3个
当质数为3,5时,计算各有1个
C++ 代码
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int n;
int vis[N]; // 筛选素数时的中间数组,不是素数就标记1
int zs[N]; //素数数组
int k; //表示1-n的数中,素数的个数
void zhi(int n) // 埃及筛
{
for(int i=2;i*i<=n;i++){
if(!vis[i]){
for(int j=i*i;j<=n;j=j+i){ // 成倍数关系的都不是素数,标记为1
vis[j]=1;//非素数
}
}
}
k=0; //素数个数初始化为0
for(int i=2;i<=n;i++){ //查找是否为素数
if(!vis[i]){ //是素数
zs[k++]=i; //存入素数数组
}
}
}
int cal(int n,int p){ //查找1-n中质数因子p的个数
int cnt=0;
while(n){
cnt=cnt+n/p;
n=n/p;
}
return cnt;
}
int main()
{
cin >> n;
zhi(n); // 埃及筛筛选素数存入数组
for(int i=0;i<k;i++){
int p=zs[i]; // 对于每一个质因子
int cnt=cal(n,p); //计算质因子的个数
cout << p << " " << cnt << endl;
}
return 0;
}