求n以內的素數，可以用試除法或者埃拉托斯特尼篩法（埃氏篩法）

輸入：數字n
輸出：n以內所有的素數

不管是哪個方法，都有一個數學結論可以減少循環次數：

如果有一個數不是質數，那么它至少有一個因子小于等于他的平方根。所以說n有因數的話，一定有一個小于根號n，因此只需要看遍歷到根號n即可。
反過來說，如果根號n內沒有某個數的因數，那么整個2，n-1都沒有這個數的因數。

試除法

使用i*i而不是sqrt(n)是為了避免對浮點數進行處理。

/**
*  試除法
*  0、1 都不是質數
*  如果有一個數不是質數，那么它至少有一個因子小于等于他的平方根
*  算法效率從n變為根號n
*/
int isPrime(int n){if(n<2) {return 0;}for(int i=2;i*i<=n;i++){if(n%i==0){return 0;}}return 1;
}
void findPrimesByTrialDivision(int n){for (int i = 2; i <= n; i++) {if (isPrime(i)) {printf("%d\t", i);}}printf("\n");
}

埃拉托斯特尼篩法（埃氏篩法）

質數的倍數一定是非質數。從而逐步將非質數排除。
由于：如果有一個數不是質數，那么它至少有一個因子小于等于他的平方根。
所以：外層循環從2-根號n，內層循環從i*i開始。

void Eratosthenes(int n){int *isPrime = calloc(n+1,sizeof(int));for(int i=2;i<=n;i++){// 初始化所有數都是質數isPrime[i] = 1;}for(int i=2; i*i<=n;i++){if(isPrime[i]){for(int j=i*i;j<=n;j+=i){isPrime[j] = 0;}}}for (int i = 2; i <= n; i++) {if (isPrime[i]==1) {printf("%d\t", i);}}printf("\n");
}

兩種方法測試

int main(){int n=20;Eratosthenes(n);findPrimesByTrialDivision(n);return 0;
}

運行效率

我們把打印質數的代碼刪掉，打印下運行時間

int main() {int n = 6000000;start = clock();Eratosthenes(n);finish = clock();time1 = (double) (finish - start) / CLOCKS_PER_SEC;printf("埃氏篩法所用時間: %f\n", time1);start = clock();findPrimesByTrialDivision(n);finish = clock();time2= (double) (finish - start) / CLOCKS_PER_SEC;printf("試除法所用時間: %f\n", time2);return 0;
}

可以看到埃氏篩法確實在數據量大的的時候效率更高。