[C Programming] 因數分解

對於一個大於2的正整數而言，
我們一定可以將其分解成一或多個質因數的乘積和。
請寫一個程式，將輸入的數分解，
輸出格式以括號表示該因數的次方數，
例如：輸入:240  輸出:2(4)3(1)5(1)     (即240=(2^4)*3*5)

解：
最基本的想法，是我們從2開始，嘗試將每一個數都去除它，
此時會有幾種狀況：
1.餘數等於0 => 整除，繼續使用同一個數嘗試去除。
2.餘數不等於0 => 不整除，將嘗試的數遞增。
持續上面的動作一直到值被除到等於1的時候，
就表示分解完畢可以輸出結果。

另一方面，由於2的倍數除了2以外都是質數，
我們可以讓嘗試的數以2、3、5、7、9...的方式來嘗試。

以這個方法而言，我們可以保證得出來的因數分解，
絕對是質因數分解。
何以見得？
(下面所提的所有數全部都是正整數)
首先我們不用考慮2的倍數會不會出現，因為迴圈中本來就不使用。
再者，如果合成數p在迴圈中被使用，
且有作為因數分解到，
設p = r*q ，r為質數，q為1以外的正整數。
既然如此，那麼因為r < p，所以迴圈中一定會先使用到r來除。
如此一來，假設所求數n = (r^i) * k， ( i >= 1, k>=1)，
那麼r^i的部分一定會被r除盡。
對於p來說，它並沒有辦法整除剩下的k；
因此產生矛盾，所以我們得證在因數分解中，
這個方法最後輸出的所有因數均為質因數。

在程式中，我們可以選擇每次找到一項質因數及其平方，
就進行輸出，如此一來，我們就不需要使用陣列來記錄。
優點當然是會省去記錄質因數及次方數的陣列，
缺點則是輸出過以後沒有任何留存。
我們直接進行輸出，這是延伸問題的第4題所要求的，
如果需要記錄陣列的話，可以比照類似昨天線性篩法附帶的因式分解來處理。
請見線性篩法-延伸(下)。
不過，在延伸問題2的時候有可能會用到需要記錄的架構，
到那時候再用那個方式處理吧XD

Code：

#include <stdio.h>
#include <stdlib.h>

void factor(unsigned long n)
{
 unsigned long i, j, work;
 
 printf("\n%ld = ", n);
 // Deal with 2 First
 // work和0x01UL(也就是1)進行&運算也就是work的最後一位為0時這項才為真(偶數)。
for(i=0, work=n; (work & 0x01UL)==0 && work > 1; work>>=1, i++) ;
 if(i) // NOT zero
  printf("%ld(%ld)",2,i);
 for(j=3; j<=work; j+=2){
  for(i=0; work%j==0 && work > 1; work/=j, i++)
  ; // 這個分號是為了避免if被當作是內層for所要做的事情。
  if(i) // 有分解到的狀況就輸出這項的分解
   printf("%ld(%ld)",j,i);
 }
}

int main(int argc, char *argv[])
{ 
 int i, n = 500;
 for(i=2;i<=n;i++)
  factor(i);
 system("PAUSE");
 return 0;
}