因子和階乘，因子階乘

因子和階乘，因子階乘

輸入正整數n（2<=n<=100),把階乘n!=1*2*3*····*n分解成素因子相乘的形式，從小到大輸出各個素數（2、3、5、···）的指數。例如825 = 3*5^2*11應表示成（0,1,2,0,1），表示分別有0、1、2、0、1個2、3、5、7、11。你的程序應該忽略比最大素因子更大的素數（否則末尾會有無窮多個0）。

樣例輸入：

5

53

樣例輸出:

5! = 3 1 1

53! = 49 23 12 8 4 4 3 2 2 1 1 1 1 1 1 1

程序：

#include <iostream>

#include <cstring>

using namespace std;

//素數判定。注意：n不能太大

int is_prime(int n)

{  

　　for(int i = 2; i*i <= n; i++)

　　 if(n % i == 0) return 0;

　　  return 1;

}

//素數表

int prime[100], count = 0;

int main()

{  

　　//n和各個素數的指數  

　　int n, p[100];    

　　//構造素數表  

　　for(int i = 2; i <= 100; i++)

 　　if(is_prime(i)) prime[count++] = i;

   while(cin >> n)

 {   

　　cout << n << "!" << "=";  

 　　memset(p, 0, sizeof(p));

  　　int maxp = 0;  

 　　for(int i = 1; i <= n; i++)

  　　{    

　　　　//必須把i復制到m中，而不要在做除法時直接修改它  

 　　　　 int m = i;    

　　　　　　for(int j = 0; j < count; j++)  

  　　　　　　while(m % prime[j] == 0) //反復除以prime[j],並累加p[j]

   　　　　　　{    

 　　　　　　　　m = m / prime[j];

   　　　　　　　　 p[j]++;   

  　　　　　　　　if(j > maxp) maxp = j;   //更新最大素因子下標

   　　　　　　}  

　　　 }  

 //只循環到最大下標

  for(int i = 0; i <= maxp; i++)  

 cout << " " << p[i];  

 cout << endl;

 }  

return 0;

}