问题描述

自然数N的阶乘(写成N!)被定义成从1到N的所有整数的乘积。例如： 5!=5X4X3X2X1=120 。 随着数N的增大，N!增长得非常快，5!=120, 10!=3628800。要列举那么大的数， 可用下列方法：不是直接列出该数，而是按照顺序列举出该数中各个质数因子出现的 次数，如825可描述为(01201)，意思是对825分解质因数，这些质数因子中有0个2，1个3，2个5，0个7，1个11。

编一程序，读入N值，按顺序输出N!所包含的质数因子的个数。

思路

我们知道，将一个数进行分解质因数，则可以这样：x=2~sqrt(n)，如果n可以除尽x，则不断除以x，伪代码如下

for(int j=2; j<=sqrt(n); j++) //枚举x
		while(n%j==0) //当前这个数可以除尽x
			n=n/j；//不断除

那这样为什么可以这样求质因子呢？ 我们知道，一个数的因子（除本身）一定比它小，那我们在试着除以当前x这个数时，如果它不是质数，那他所有的因子在之前就已经全部去除了，因此不会再可以除尽 根据这个思路，我们就可以开始写了

代码

#include <bits/stdc++.h>
using namespace std;
int a[1000001],n;
void kk(int n) {//分解质因数 
	for(int j=2; j<=sqrt(n); j++) {//从2枚举到sqrt（n) 
		while(n%j==0) {//不断除 
			a[j]++;//把当前质因子用桶装起来 
			n=n/j;
		}
	}
	a[n]++;//千万注意，n最后也是一个质数，在分解后要把a[n]也++ 
	return;
}
int main() {
	cin>>n;
	for(int i=2; i<=n; i++) kk(i);//阶乘，每个数都分解质因子 
	for(int i=2; i<=n; i++)
		if(a[i]>0) cout<<a[i]<<" ";//如果有当前因子，输出 

	return 0;
}

这里要注意，不能阶乘后再分解，那样会爆（阶乘后数字巨大）

这样的话，时间复杂度就很少了。