[C Programming] 篩法-延伸

請參照篩法問題。
延伸：
1. 為什麼在程式工作過程中，如果sieve[i]為KEPT時，
　2i+3就是一個質數？
2. 請分析一下程式一共查過了多少個元素。
3. 連3的倍數都不處理的話，每6個數剩下的就只有6n+1, 6n+5而已，
    換句話說只要處理原來的三分之一的元素就行了。
    請把這個觀念寫成程式。

額外(個人討論)：
4.將程式改寫成只篩到N/2就結束，同樣要輸出質數及總數目。

個人解答：
1. 在查到第i個的時候，表示已經用所有前面的數篩過了，
    既然到這裡沒有被篩掉，那麼就表示其沒有質因數，
    所以2i+3就是一個質數。
2. 首先程式要每一個數經過(共n次)，
    再來每次濾掉2i+3的倍數，
    就是n/3 + n/5 + n/7 + ...也就是n*(n以內質數的倒數和-1/2)。
    兩者相加就剛好是n*(n以內的質數的倒數和)。
    n越大的時候其實它會發散就是了= =......
3.
對於前一個程式而言，x[i]=2i+1，
我們每一次移動1單位的index跳的值是2。
如果我們要直接去用6i+1和6i+5來記錄，
單位的移動會變得很難掌握。
我們可以改成，
一開始將全部都設為KEPT，
接著把所有3的倍數再設為DELETED。
除3以外剩下為KEPT的是5、7、11、13、17、...
也就是從x[1]開始每次值是2、4、2、4的移動，
index則是1、2、1、2的移動。
換句話說，
在x[]中的初始樣態應該長這樣：
index:     0  1  2  3  4   5   6   7   8   9  10  11
代表值:  3  5  7  9  11 13 15 17 19 21 23 25
K/D:      K  K  K  D  K   K  D   K  K   D   K   K

接下來，在迴圈中的移動，
我們就直接跳著來做篩選就好，
比照之前的dist，這次初始的i是1，
dist是1，做完後要以dist = 3-dist來改變位移量。
同時參照4.來控制範圍，節省的更多。
Code部分的變化:

 int range = n/2, dist = 1, cnt = 1, KEPT = 1, DELETED = 0;
 for(i = 0; i <= n; i++)
  x[i] = KEPT;
 for(i = 3; i <= n; i+=3)
  x[i] = DELETED;
 i = 1;
 while( i <= range )
 {
  if(x[i])  // If KEPT -> start to sieve
  {
   tmp = i+i+3; // Each time index moves 2i+3
   for(j = i+tmp; j <= n ; j += tmp) 
    x[j] = DELETED;
  }
  i += dist;
  dist = 3 - dist;
 }
   

4. 宣告一個變數range = n/2，並且將for迴圈條件改成for(i = 0; i <= range; i++)。

    篩完以後，再使用迴圈加總count。
    相較於原程式，多了一次走訪全陣列，少去了篩大於n/2的倍數，
    整體而言，當n越大，這個方法就越節省時間。
額外增加的Code：

 for(i = 0; i <= n; i++)
  if(x[i]) 
   cnt++;