阶乘分解质因数

给定整数 N，试把阶乘 N!分解质因数，按照算术基本定理的形式输出分解结果中的 pi 和 ci 即可。

输入格式

一个整数 N。

输出格式

N! 分解质因数后的结果，共若干行，每行一对 pi,ci，表示含有 pi^ci 项。按照 pi 从小到大的顺序输出。

数据范围

1≤N≤10^6

输入样例：

5

输出样例：

2 3
3 1
5 1

样例解释

5!=120=23∗3∗5

转载：https://www.cnblogs.com/Slager-Z/p/7780382.html

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int prime[maxn];
int vis[maxn];
int cnt;
int oula(int n)
{for(int i = 2;i<=n;i++){if(!vis[i])prime[++cnt]=i;for(int j = 1;j<=cnt&&i*prime[j]<=n;j++){vis[i*prime[j]]=1;if(i%prime[j]==0){break;}}}
}
int main()
{int n;cin>>n;oula(n);for(int i = 1;i<=cnt;i++){int tempN = n,nowPrime=prime[i],nowAns = 0;while(tempN){nowAns+=(tempN/nowPrime);tempN/=nowPrime;}cout<<nowPrime<<" "<<nowAns<<endl;}return 0;
}