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

請參照線性篩法。
由於2的部分我還需要花點時間確認其正確性，
因此將其分開來解答。
敬請期待XD~

延伸問題：
1. 這個程式花了一半的時間將2到n之間的偶數刪去，
    但這其實是多餘的，因為除了2以外，
    所有的偶數都不是質數。
    請修改此地的程式，讓它不處理2以外的偶數，
    因此省下一半的時間。(2與n之間一半元素是偶數)
    可參照前面使用一般篩法的想法。
2. 此地的記憶體用量明顯比上一題的傳統篩法大許多。
    可否將它作節省呢？
　首先我們不要prev[]只留下next[]，那對於next[i]來說，
    如果i-1沒有被刪除，那i的上一個是i-1，但若i-1已經被刪除了，
    我們用next[i-1]來存原來的prev[i]，換句話說，
    i的上一個就是i-1與next[i-1]中值較少的那一個。
    請問，還有什麼邊界條件要考慮，並且將此概念寫成程式。
    這個技巧在第一個問題之下能否適用呢？
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給分解完成。

個人解答：
1. 因為目的是省時間，我們只要在一開始的時候，
    將每一個next和prev跳著接就好了。
    也就是說，每次的next[i]=i+2, prev[i]=i-2;
    除了要注意next[2]=3, prev[3]=2,
    而且最後的n要視其是否為偶數來定位prev。
    這樣相當於我們完全直接跳過了偶數的部分(直接刪掉。)
Code：
首先我們在INITIAL(n)之前先加入此式使其成為奇數：

n -= (n-1)%2;  // make sure odd

接下來，把prime=2的初始條件改為3，並且更改INITIAL：

#define INITIAL(n) { unsigned long i;    \
    for(i=3; i<=n; i+=2)      \
     prev[i]=i-2, next[i]=i+2; \
    prev[2]=next[n]=NULL;   \
    next[2]=3, prev[3]=2;   \
  }