[C Programming] 因數分解-延伸

請參照因數分解。
延伸問題：
1. 程式中都有work>1的測試，究竟這有沒有必要？
    請說明你的理由。
2. 在第二個for迴圈中，我們分別用k=3,5,7,9,11,13,...去除，
    但事實上用3去除時已經去掉所有3的倍數了，
    因此再用9、15等數去除自然不可能再整除，
    所以我們等於做了多餘的事情。請修改這個程式，
    使得只會用質數去除，因此9,15,...等就不會出現了。
3. 請問，這個程式所輸出的因數為什麼都是質數？請證明它。
4. 在程式中，其實factor[]與exps[]，
    這兩個用來存放因數與對應的指數的陣列是不必要的。
    為什麼？請修改程式，不用這兩個陣列，但效果完全相同。
個人解答：
1. 沒有必要。work不斷去除以k的時候，
    最後一定會讓work變成1，從而不符合work%k == 0的迴圈繼續條件。
2. 我們可以利用前面的篩法的概念，先將合成數全部篩掉。
    首先開出陣列且初始化為0，
    簡單的使用倍數的方式，由3開始，將所有合成數都標記為1。
    如此一來，在陣列中所有的奇數且為合成數的都會被標記為1。
    在求因數的時候，先檢查標記是否為0，不是的情況下再行做除法。
    下面Code範例是求出從2到50的因數分解。
Code：

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

#define MAXSIZE 50
void factor(unsigned long n, unsigned long *fact)
{
 unsigned long i, j, work;
 printf("\n%ld = ", n);
 // Deal with 2 First
 for(i=0, work=n; (work & 0x01UL)==0 ; work>>=1, i++) ;
  
 if(i) // NOT zero
  printf("%ld(%ld)",2,i);
 for(j=3; j<=work; j+=2){
  if(fact[j]==0)
   for(i=0; work%j==0 ; work/=j, i++)
   ;
  if(i)
   printf("%ld(%ld)",j,i);
 }
}

int main(int argc, char *argv[])
{ 
 unsigned long i, j, n = MAXSIZE, fact[MAXSIZE+1]={0};
 for(i=3;i<=MAXSIZE;i+=2)
  if(fact[i]==0)
   for(j=i<<1;j<=MAXSIZE;j+=i)
    if(fact[j]!=1)
     fact[j] = 1; 
 for(i=2;i<=n;i++)
  factor(i, fact);
 printf("\n");
 system("PAUSE");
 return 0;
}

3. 如果輸出的因數具有合成數q=p*r,其中p為質數：
    那麼q>p，所以p在迴圈中一定會先被拿來做為work/=k中的k來使用。
    既然迴圈只要在work%k==0的狀況下就會持續，
    那麼所有存在p為因數的數，在經過k=p的迴圈時，p的因子皆會被除盡，
    因此q再拿來當作k來嘗試時，不可能除盡，因此輸出中不會出現，矛盾。
    故不存在合成數能作為輸出的因數。
4. 在基本題的用法就是不用陣列的做法。
    明顯的優點是節省空間，缺點就是只能輸出而沒有記錄。