[C Programming] 線性篩法-延伸(下)

3. 在這裡我們來看看如何修改本問題，
    而同時求出2到n之間每一個數的因數分解，
    這是Dexter Kozen提出來的方法。
    因為每個合成數r都可以寫成p^i * q的形式，
    p為r最小的質因數。
    當要刪除r時，我們在程式中就會知道p、i、q的值，
    我們可以準備三個陣列來存P[r]、EXP[r]、Q[r]。
    只要先將P[]初始化成0，在程式執行完後，
    P[r]=0的r肯定是質數，其他的狀況則為合成數。
    那我們知道r^i次方的部分，接著再往下找P[Q[r]]，
    一路找下去就可以將r給分解完成。

個人解答：
我們將輸出的格式定為如下：
60 = 2(2)3(1)5   (括號內的數為次方項)
在這種狀況下，我們為了要求每一個數的因數分解，
那麼就沒辦法無視2的倍數了。
所以前面只用next方法依舊是可以用，
但初始化時要改為每次+1，且LEFT(x) 改為x-1。
這裡就直接使用最原本的線性篩法來解答。
在三重迴圈中，除了相應的陣列外，
我們多加了一個pcnt，每次從新的q開始時就要重置，
而在第三層迴圈是每次乘上pcnt，自然要進行遞增。
當我們要進行刪去時，
有兩種情況：
1. prime == q
這種情況下p^pcnt*q相當於p^(pcnt+1)，
因此給值P[mult]=prime,EXP[mult]=pcnt+1,Q[mult]=1
2. prime  <  q
給值P[mult]=prime,EXP[mult]=pcnt,Q[mult]=q

然後在讀取每一個數的時候，分下列三種狀況：
1. P[i] == 0
主程式中由於我們會先用迴圈對陣列初始化為0，
因此當碰到0的狀況時，表示它已經是質數了，
因此就輸出這個數本身即可。
2. Q[i] == 1
這個狀況代表說這個數為p的EXP[mult]，
那麼只要輸出P[mult](EXP[mult])即可。
3. else
除此以外的狀況，表示在將p^i的部分表示出來以後，
q還可以被分解，那麼就用遞迴的方式，
將Q[mult]做為參數傳遞進去，最後就可以完全分解。



Code：

void L_Sieve(unsigned long n,unsigned long *P,unsigned long *Q,unsigned long *EXP)
{
 unsigned long prev[MAXSIZE+1], next[MAXSIZE+1];
 unsigned long prime, q, i, mult, cnt = 0;
 unsigned long pcnt;
 INITIAL(n);
  
 for(prime=2; prime*prime <= n; NEXT(prime))
  for(q=prime, pcnt=1; prime*q <= n; NEXT(q), pcnt=1)
   for(mult=prime*q; mult <= n; mult*=prime, pcnt++)
   { 
    if(prime==q){
     P[mult] = prime; EXP[mult] = pcnt+1; Q[mult] = 1;
    }
    else{
     P[mult] = prime; EXP[mult] = pcnt; Q[mult] = q;
    }
    REMOVE(mult);
   }
 
 for(i = 2; i!= NULL; NEXT(i))
 {
  if(cnt % 8 == 0) printf("\n");
  printf("%6ld", i);
  cnt++;
 }
 printf("\n\nTotal Prime Count: %ld \n", cnt);
}
void factor(unsigned long i, unsigned long *P, unsigned long *Q, unsigned long *EXP){
  if(P[i]==0) 
   printf("%ld", i);
  else if(Q[i] == 1){
   printf("%ld(%ld)", P[i], EXP[i]);
  }
  else{
   printf("%ld(%ld)", P[i], EXP[i]);
   factor(Q[i],P,Q,EXP);
  } 
}

int main(int argc, char *argv[])
{
 // Initializing.
 unsigned long P[MAXSIZE+1], EXP[MAXSIZE+1], Q[MAXSIZE+1];
 unsigned long i;
 for(i=2;i<=MAXSIZE+1;i++){
  P[i]=EXP[i]=Q[i]=0;
 }
 
 L_Sieve(MAXSIZE,P,Q,EXP);
 for(i=2;i<=MAXSIZE;i++){
  printf("%ld = ",i); 
  factor(i,P,Q,EXP);
  printf("\n");
 }
 system("PAUSE");
 return 0;
}