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