求解一個(gè)算法，我們首先要知道它的數(shù)學(xué)含義。依據(jù)這個(gè)原則，首先我們要知道什么是素?cái)?shù)。; 素?cái)?shù)是這樣的整數(shù)，它除了表示為它自己和1的乘積以外，無(wú)論他表示為任何兩個(gè)整數(shù)的乘積。

　　找素?cái)?shù)的方法多種多樣。

　　1:是從2開(kāi)始用"是則留下，不是則去掉"的方法把所有的數(shù)列出來(lái)(一直列到你不想再往下列為止，比方說(shuō)，一直列到10,000)。個(gè)數(shù)是2,它是一個(gè)素?cái)?shù)，所以應(yīng)當(dāng)把它留下來(lái)，然后繼續(xù)往下數(shù)，每隔一個(gè)數(shù)刪去一個(gè)數(shù)，這樣就能把所有能被2整除、因而不是素?cái)?shù)的數(shù)都去掉。在留下的小的數(shù)當(dāng)中，排在2后面的是3,這是第二個(gè)素?cái)?shù)，因此應(yīng)該把它留下，然后從它開(kāi)始往后數(shù)，每隔兩個(gè)數(shù)刪去一個(gè)，這樣就能把所有能被3整除的數(shù)全都去掉。下一個(gè)未去掉的數(shù)是5,然后往后每隔4個(gè)數(shù)刪去一個(gè)，以除去所有能被5整除的數(shù)。再下一個(gè)數(shù)是7,往后每隔6個(gè)數(shù)刪去一個(gè);再下一個(gè)數(shù)是11,往后每隔10個(gè)數(shù)刪一個(gè);再下一個(gè)是13,往后每隔12個(gè)數(shù)刪一個(gè)。就這樣依法做下去。

　　但是編程我們一般不采用上面的方法，并不說(shuō)這中方法計(jì)算機(jī)實(shí)現(xiàn)不了，或者說(shuō)實(shí)現(xiàn)算法比較復(fù)雜。因?yàn)樗褚粋€(gè)數(shù)學(xué)推理。我們也給一個(gè)算法。

　　下面我們介紹幾種長(zhǎng)用的編程方法。

　　2:遍歷2以上N的平方根以下的每一個(gè)整數(shù)，是不是能整除N;(這是基本的方法)

　　3:遍歷2以上N的平方根以下的每一個(gè)素?cái)?shù)，是不是能整除N;(這個(gè)方法是上面方法的改進(jìn)，但要求N平方根以下的素?cái)?shù)已全部知道)

　　4:采用Rabin-Miller算法進(jìn)行驗(yàn)算;

　　例如：N=2^127-1是一個(gè)38位數(shù)，要驗(yàn)證它是否為素?cái)?shù)，用上面幾個(gè)不同的方法：

　　驗(yàn)算結(jié)果，假設(shè)計(jì)算機(jī)能每秒鐘計(jì)算1億次除法，那么

　　算法2要用4136年，算法3要用93年，算法4只要不到1秒鐘!(這些數(shù)據(jù)是通過(guò)計(jì)算得到)

　　另外印度有人宣稱素?cái)?shù)測(cè)試是P問(wèn)題，我一直沒(méi)有找到那篇論文，聽(tīng)說(shuō)里面有很多數(shù)學(xué)理論。如果那位大人有這篇論文，麻煩轉(zhuǎn)發(fā)一份。

　　下面我們分別實(shí)現(xiàn)上面的三種算法：

　　以下算法我們不涉及內(nèi)存溢出，以及大數(shù)字的問(wèn)題。如果測(cè)試數(shù)字超過(guò)2^32,發(fā)生內(nèi)存溢出，你需要自己使用策略解決這個(gè)問(wèn)題，在這里只討論32位機(jī)有效數(shù)字算法。

　　1: 算法0:是從2開(kāi)始用"是則留下，不是則去掉"的方法把所有的數(shù)列出來(lái)

　　數(shù)組中不為0的數(shù)字就是要查找的素?cái)?shù)。

　　void PrimeNumber0()

　　{

　　int time GetTickCount();

　　cout start time time endl;

　　int Max[MAX_NUMBER]; 在棧上分配，棧上空間要求一般都在2M之間，

　　如果你需要更大空間，請(qǐng)?jiān)诙焉仙暾?qǐng)空間(就是通過(guò)malloc,new來(lái)申請(qǐng))。

　　memset(Max,0,MAX_NUMBER);

　　for(int i = 0 ; i MAX_NUMBER; ++i)