第4题 阶乘因子(yinzi) 时限：1s 空间：256m Description

桐桐刚刚学习了自然数N的阶乘（N!）：被定义成从1到N的所有整数的乘积。例如5!=54321=120，随着数N的增大，N!增长的非常快，5!=120，10!=3628800。桐桐想到了一种方法来列举那么大的数：不是直接列出该数，而是按照顺序列举出该数中各个质数因子出现的次数，如825可描述为（0 1 2 0 1），意思是对825分解质因数，这些质数因子中有0个2，1个3，2个5，0个7，1个11。请你编一个程序，读入N值，帮助桐桐按顺序输出N!所包含的质数因子的个数。

Input

只包含1个数N（2<=N<=100000）

Output

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

Sample Input

53

Sample Output

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

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstring>
using namespace std;
int n,a[100005],p[100005],tmp;
int main() {
	scanf("%d", &n);
	for(int i = 4; i <= n; i += 2) {
		tmp = i;
		while(!(tmp & 1)) tmp/=2, a[2]++;
		p[i] = 1;
	}
	printf("%d", a[2] + 1);
	for(int i = 3; i <= n; i += 2) {
		if(p[i]) continue;
		for(int j = i + i; j <= n; j += i) {
			tmp = j;
			while(!(tmp % i)) tmp /= i, ++a[i];
			p[j] = 1;
		}
		printf(" %d", a[i] + 1);
	}
	return 0;
}