Eratosthenes篩選求質數

除了自身之外，無法被其它整數整除的數稱之為質數，要求質數很簡單，但如何快速的求出質數則一直是程式設計人員與數學家努力的課題，在這邊介紹一個着名的 Eratosthenes求質數方法。

解法首先知道這個問題可以使用回圈來求解，将一個指定的數除以所有小于它的數，若可以整除就不是質數，然而如何減少回圈的檢查次數？如何求出小于N的所有質數？

首先假設要檢查的數是N好了，則事實上隻要檢查至N的開根号就可以了，道理很簡單，假設A*B = N，如果A大于N的開根号，則事實上在小于A之前的檢查就可以先檢查到B這個數可以整除N。不過在程式中使用開根号會精确度的問題，是以可以使用 i*i <= N進行檢查，且執行更快。

再來假設有一個篩子存放1～N，例如：

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ........ N

先将2的倍數篩去：

2 3 5 7 9 11 13 15 17 19 21 ........ N

再将3的倍數篩去：

2 3 5 7 11 13 17 19 ........ N

再來将5的倍數篩去，再來将7的質數篩去，再來将11的倍數篩去........，如此進行到最後留下的數就都是質數，這就是Eratosthenes篩選方法（Eratosthenes Sieve Method）。

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

#define N 1000 

int main(void) { 
    int i, j; 
    int prime[N+1]; 

    for(i = 2; i <= N; i++) 
        prime[i] = 1; 

    for(i = 2; i*i <= N; i++) { // 這邊可以改進 
        if(prime[i] == 1) { 
            for(j = 2*i; j <= N; j++) { 
                if(j % i == 0) 
                    prime[j] = 0; 
            } 
        } 
    } 

    for(i = 2; i < N; i++) { 
        if(prime[i] == 1) { 
            printf("%4d ", i); 
            if(i % 16 == 0) 
                printf("\n"); 
        } 
    } 

    printf("\n"); 
    return 0; 
}