轉自：http://www.doforfun.net/article/20090504/543.htm
經常有初學者詢問求解N內所有素數（質數）的問題，對此，網上的解答也很多，但很多要么不夠專業，要么只有程序沒有算法解析，所以三藏大廈對此問題做個小結，探討一下求解素數的常見算法，同時給出相應的C語言程序及其解析。為了方便初學者理解，本文將從易到難闡述不同算法，高手可以直接看后面的高效算法
質數的定義
一個數，如果只有1和它本身兩個因數，這樣的數叫做質數，又稱素數。
試除判斷法
算法描述：從上述定義可知，素數不能被1和它本身之外的數整除，所以，判斷一個數x是否素數只要看它是否能被2~sqrt(x)間的數整除即可；而求N內所有素數則是循環重復上述過程。
C語言實現：
#include <time.h>
#include <malloc.h>
#define N 100000
// 簡單試除判斷法 Ver1
int SimpleDivisionV1(int n)
{
int i,j;
// 素數數量統計
int count = 0;
// 分配存放結果的空間
int* primes = (int*)malloc( sizeof(int)*n );
// 2是素數誰都知道，不算了
primes[count++] = 2;
// 循環計算3~n間的數
for (i=3; i<=n; i++)
{
// 為什么是sqrt(i)，思考一下
for (j=2; j<=sqrt(i); j++)
{
// i被j整除，顯然不是素數了
if (i%j == 0) break;
}
// i不能被2~sqrt(i)間的數整除,素數也
if (j > sqrt(i))
{
primes[count++] = i;
}
}
// 因輸出費時，且和算法核心相關不大，故略
// 釋放內存，別忘了傳說中的內存泄漏
free(primes);
return count;
}
void main()
{
int count;
clock_t start, end;
// time函數不夠精確，用clock湊合一下吧
start = clock();
count = SimpleDivisionV1(N);
end = clock();
printf("[%d]以內素數個數：%d, 計算用時：%d毫秒\n", N, count, end-start);
getch();
}
計算結果：
[100000]以內素數個數：9592, 計算用時：468毫秒
[1000000]以內素數個數：78498, 計算用時：10859毫秒
[5000000]以內素數個數：348513, 計算用時：103560毫秒
噢噢，算算十萬還行，百萬就10秒多了，而且時間增長很快，這不行，得優化一下！
優化分析：
仔細研究一下SimpleDivisionV1我們可以發現以下幾個問題：
- 在循環條件中重復調用sqrt(i)顯然是比較浪費時間的
- 判斷素數，真的需要拿2~sqrt(i)間的所有整數去除嗎？我們知道，合數都可以分解成若干質數，所以只要2~sqrt(i)間的質數不能整除i即可
根據上面兩點，我們可將SimpleDivisionV1升級為SimpleDivisionV2，如下
// 簡單試除判斷法 Ver2
int SimpleDivisionV2(int n)
{
int i, j, k, stop;
// 素數數量統計
int count = 0;
// 分配存放結果的空間
int* primes = (int*)malloc( sizeof(int)*n );
// 2是素數誰都知道，不算了
primes[count++] = 2;
stop = count;
// 循環計算3~n間的數
for (i=3; i<=n; i++)
{
k = sqrt(i);
// 在循環條件中重復調用sqrt是低效做法，故引入k
while (primes[stop] <= k && stop < count)
stop++;
// stop干什么用，思考一下
for (j=0; j<stop; j++)
{
if (i%primes[j] == 0) break;
}
// i不能被2~sqrt(i)間的素數整除，自然也不能被其他數整除,素數也
if (j == stop)
{
primes[count++] = i;
}
}
// 因輸出費時，且和算法核心相關不大，故略
// 釋放內存，別忘了傳說中的內存泄漏
free(primes);
return count;
}
然后將main中調用的函數替換為SimpleDivisionV2，在看一下執行結果：
[100000]以內素數個數：9592, 計算用時：46毫秒
[1000000]以內素數個數：78498, 計算用時：546毫秒
[5000000]以內素數個數：348513, 計算用時：3515毫秒
[10000000]以內素數個數：664579, 計算用時：8000毫秒
很開心的看到，經過優化，速度提高了幾十倍，尤其是時間增長曲線的坡度變小了，N值越大，V2函數比V1的效率就越高
對于試除判斷這種質數算法來說，三藏認為SimpleDivisionV2基本已經接近極限，不大可能有量級上的突破了，有興趣的朋友可以自己進一步優化。初學者除了參看上述例子外，可以嘗試做各種修改及細節優化，也可以將除法變乘法，多加練習是學習編程的好方法。
雖然，上例中V2已經比V1快了很多了，但隨著N的增大，耗時還是不少，那么我們還有更好的方法嗎？