因子和阶乘

时间限制：

1000

 ms  |  内存限制：

65535

 KB

难度：

2

 

描述

给你一个正整数n，把n!=1x2x3x.....xn分解成素因子相乘的形式，并从小到大输出每个素因子的指数，但要保证最后输出的素因子个数不为0。例如825应表示为0,1,2,0,1表示分别有0,1,2,0,1个2,3,5,7,11。

 

输入

第一行有一个整数n(0<n<10000),表示有n组测试数据；

接下来n行每行有一个整数 m(1<m<10000)

输出

从小到大输出m分解成素因子相乘后各个素因子对应的指数

样例输入

2553

样例输出

3 1 149 23 12 8 4 4 3 2 2 1 1 1 1 1 1 1

讲解：大概意思就是看n的阶乘中是用多少个素数的多少次方算的 例如825=3*5²*11所以是一个3，两个5

，一个11，然后再统计824；以此类推

代码如下：

#include<stdio.h>

#include<math.h>

#include<string.h>

int a[10000];

int main()

{

 void fun();

 int m,n,i,j,t,b[10010];

 fun();

  scanf("%d",&t);

  while(t--)

  {

   memset(b,0,sizeof(b));

   scanf("%d",&n);

   for(i=n;i>=2;i--)

   {

    for(j=0;a[j]<=i;j++)

    {  m=i;

     while(m%a[j]==0)

     {

      b[a[j]]++;

      m=m/a[j]; 

     }

    }

   }

    for(i=0;a[i]<=n;i++)

     if(b[a[i]])

      printf("%d ",b[a[i]]);

     printf("\n");

  }

  return 0;

}

void fun()

{

 int i,m,k,c=1,j;

 a[0]=2;

 for(i=3;i<=10000;i++)

 { k=0;

  m=i;

  for(j=2;j<=sqrt(m);j++)

   if(m%j==0)

   {

    k=1;

    break;

   }

   if(k!=1)

    a[c++]=i;  

 }

// for(i=0;i<=10000;i++)

//  printf("%d ",a[i]);

}