对N!进行质因子分解。
输入格式：
输入数据仅有一行包含一个正整数N，N<=10000。
输出格式：
输出数据包含若干行，每行两个正整数p,a，中间用一个空格隔开。表示N!包含a个质因子p,要求按p的值从小到大输出。
10!=3628800=(2^8)*(3^4)*(5^2)*7
与数论硬刚到底。。。
质因数：质因数（或质因子）在数论里是指能整除给定正整数的质数。两个没有共同质因子的正整数称为互质。因为1没有质因子，1与任何正整数（包括1本身）都是互质。正整数的因数分解可将正整数表示为一连串的质因子相乘，质因子如重复可以指数表示。根据算术基本定理，任何正整数皆有独一无二的质因子分解式。只有一个质因子的正整数为质数。
举几个例子吧
6的质因数是2和3
2,4,6,8的质因数只有2
那么对于这道题来说，我们只要分解阶乘的每一位就好了（真的算完的话会炸）
完整代码
#include<bits/stdc++.h> using namespace std; const int MAXN=10005; bool vis[MAXN]; int n,a[MAXN]; void su() { vis[0]=vis[1]=1; for(int i=2;i<=n;i++) if(!vis[i]) for(int j=2;i*j<=n;j++) vis[i*j]=1; } void div(int k) { int t=k; if(!vis[k]) { a[k]++; return; } for(int i=2;i<=t;i++) { if(!vis[i]) { if(k%i==0) a[i]++,k/=i,i--; } } } int main() { cin>>n; su(); for(int i=1;i<=n;i++)div(i); for(int i=1;i<=n;i++) if(a[i]) cout<<i<<‘ ‘<<a[i]<<endl; return 0; }
参考大佬@fleetingtime 的题解
原文：https://www.cnblogs.com/pcpcppc/p/9898822.html