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;
}
