题目描述

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

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

输入

只包含 $1$ 个数 $N$ $(2≤N≤100000)$。

输出

一个 $N!$ 中所包含的质数因子的个数（从最小的质数开始）的序列，数与数之间用一个空格隔开。

样例输入

53

样例输出 Copy

49 23 12 8 4 4 3 2 2 1 1 1 1 1 1 1 

代码如下：

#include <bits/stdc++.h>
#define N 100000
using namespace std;

int n;
bool prime[N+5];
int ans[N+5];

void pd(int t){
	prime[1]=1;
	for(int i=2;i<=t;i++){
		if(prime[i]==0){
			for(int j=2;i*j<=t;j++){
				prime[i*j]=1;
			}
		}
	}
}

void fjzys(int x){
	int r=2;
	if(prime[x]==0){
		ans[x]++;
		return ;
	}
	while(x>1){
		while(prime[r]==1) r++;
		while(x%prime[r]==0){
			x/=prime[r];
			ans[r++]++;
		}
	}
}

int main(){
	scanf("%d",&n);
	pd(n);
	for(int i=2;i<=n;i++){
//		printf("%d\n",i);
		fjzys(i);
	}
	for(int i=2;i<=n;i++){
		if(prime[i]==0&&ans[i]>0) printf("%d ",ans[i]);
	}
	return 0;
}