《算法競賽入門經典》5.42數學基礎-因子和階乘，算法競賽入門經典
輸入正整數n（2<=n<=100），把階乘n!=1*2*3*…*n分解成素因子相乘的形式，從小到大輸出各個以（2、3、4、5…）的指數。例如825=3*5*5*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
![]()
1 #include <stdio.h>
2 #include <string.h>
3 //素數判定
4 /* do NOT use this if x is very large or small
5 *n太小時n=1會被錯誤地判斷為素數，太大時i*i可能溢出
6 */
7 int is_prime(int n)
8 {
9 int i;
10 for(i = 2; i*i <= n; i++) //判斷不超過sqrt(x)的整數i
11 if(n % i ==0) return 0; //一旦發現有一個大於1的因子，立刻返回0（假）
12 return 1; //最後返回1（真）
13 }
14
15 //素數表
16 int prime[100], count = 0;
17 int main()
18 {
19 //變量i，n和各個素數的指數
20 int i, n, p[100];
21 //構造素數表
22 for(int i = 2; i <= 100; i++)
23 if(is_prime(i)) prime[count++] = i;
24 while(scanf("%d", &n) == 1)
25 {
26 printf("%d! =", n);
27 memset(p, 0, sizeof(p)); //string.h
28 int maxp = 0; //定義最大素數因子下標並賦初值
29 for(i = 1; i <= n; i++)
30 {
31 //必須把i復制到變量m中，而不要在做除法時直接修改它
32 int m = i;
33 for(int j = 0; j < count; j++)
34 while(m % prime[j] == 0) //反復除以prime[j]，並累加p[i]
35 {
36 m /= prime[j];
37 p[j]++;
38 if(j > maxp) maxp = j; //更新最大素數因子下標
39 }
40 }
41 //只循環到最大下標
42 for(i = 0; i <= maxp; i++)
43 printf(" %d", p[i]);
44 printf("\n");
45 }
46 return 0;
47 }
View Code
分析：
因am×an=a(m+n)，則只需把所有素因子對應的指數累加起來；注意到n<=100，這些素因子不會超過100，輸出時忽略到最後的0即可。
