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