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）。
?
檢查的次數還可以再減少，事實上，只要檢查6n+1與6n+5就可以了，也就是直接跳過2與3的倍數，使得程式中的if的檢查動作可以減少。
實作
#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; }?
總結
以上是生活随笔為你收集整理的Eratosthenes筛选求质数的全部內容，希望文章能夠幫你解決所遇到的問題。
