NYOJ 505 因子和阶乘

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年01月20日 星期三 13时53分54秒
  4File Name :code/nyoj/509.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define fst first
 20#define sec second
 21#define lson l,m,rt<<1
 22#define rson m+1,r,rt<<1|1
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27
 28using namespace std;
 29const double eps = 1E-8;
 30const int dx4[4]={1,0,0,-1};
 31const int dy4[4]={0,-1,1,0};
 32const int inf = 0x3f3f3f3f;
 33const int N=10500;
 34int n;
 35int pri[N]={0};
 36int npri[N]={1,1};
 37int num[N];
 38int cnt;
 39
 40void pre()
 41{
 42    cnt = 0 ;
 43    for ( int i = 2 ; i < N  ; i++)
 44    {
 45	if (!npri[i]) pri[cnt++] = i;
 46
 47	    for ( int j = 0 ; j < cnt &&i*pri[j]<N  ;j++)
 48	    {
 49		npri[i*pri[j]] = 1;
 50		if (!(i%pri[j])) break;
 51
 52	    }
 53
 54    }
 55//    for ( int i = 0 ; i <= 100 ; i++) printf("%d ",pri[i]);
 56
 57}
 58void solve ( int x)
 59{
 60    for ( int i = 2 ; i <= x ; i++)
 61    {
 62	int tmp =  i;
 63	for ( int j = 0 ; j < cnt ; j++)
 64	{
 65	    while (tmp%pri[j]==0)
 66	    {
 67		tmp/=pri[j];
 68		num[j]++;
 69
 70	    }
 71	    if (tmp==1) break;
 72	}
 73    }
 74    for ( int i = 0 ; i < cnt ; i++)
 75    {
 76	if (pri[i]>x) break;
 77	printf("%d ",num[i]);
 78    }
 79}
 80int main()
 81{
 82	#ifndef  ONLINE_JUDGE 
 83//	freopen("code/in.txt","r",stdin);
 84  #endif
 85
 86	pre();
 87	int T;
 88	cin>>T;
 89	while (T--)
 90	{
 91	    ms(num,0);
 92	    scanf("%d",&n);
 93	    solve(n);
 94	    puts("");
 95	}
 96
 97  #ifndef ONLINE_JUDGE  
 98  fclose(stdin);
 99  #endif
100    return 0;
101}