隨感而發(fā)

雜七雜八

統(tǒng)計

隨筆 - 67
文章 - 0
評論 - 132
引用 - 0

留言簿(13)

閱讀排行榜

評論排行榜

求2-nMax的素數(shù)

今天本來打算學習散列表的，看了一下，發(fā)現(xiàn)你面很多地方用到素數(shù)，所以就寫了一個求素數(shù)的程序，很有大一的感覺。呵呵。奉上源代碼：

#include <stdio.h>

#include <stdlib.h>

int g_nPrime[100000];

//求nMax范圍類最多不超過nLen個素數(shù)，把結(jié)果保存在nPrime中。

//返回素數(shù)的個數(shù)

int GetPrimeNumbers(int nPrime[], int nLen, int nMax)

{

//如果空間為0，或nMax小于2則返回沒有求道素數(shù)。

if (nMax < 2 || nLen <= 0)

{

return 0;

}

int nNumber = 1; //初始個數(shù)為1個(即2這個素數(shù))

nPrime[0] = 2;

int nPos = 0; //是除比較時候的最大下標。這樣可以節(jié)省一小小時間

for (int i = 3; i < nMax && nNumber < nLen; ++i)

{

int j;

//遍歷要除的素數(shù)，如果都不能整除，則i為素數(shù)。

for ( j = 0; j <= nPos; ++j)

{

if (i % nPrime[j] == 0)

{

break;

}

if (j > nPos ) //都不能整除，i是素數(shù)

{

nPrime[nNumber] = i; //保存到nprime中，并個數(shù)加1

++nNumber;

}

else if (j == nPos && i == nPrime[nPos] * nPrime[nPos])

{

//如果該數(shù)位最大下標對應值的平方，最大下標加1

++nPos;

}

return nNumber;

}

int main()

{

//測試一把，不過比較花，改為1000就不錯。呵呵。

int nNumber = GetPrimeNumbers(g_nPrime, 100000, 100000000);

for (int i = 0; i < nNumber; ++i)

{

printf("%d ", g_nPrime[i]);

}

system("pause");

return 0;

}

//為什么這么增加一個最大求余地下標，主要是為了提高點效率。如果一個數(shù)字在一個素數(shù)的

//平方范圍內(nèi)，則只需要對比他小的素數(shù)求余就可以了。這樣可以提高

//一點點時間。我看了一下120萬中有10萬個素數(shù)，如果加上最大求余下標，就只需到1000

//這樣的話可以省略掉1000-1百萬之間的所有素數(shù)求余，也就是省略了大概9萬個數(shù)據(jù)。很客觀的。

posted on 2009-05-04 19:42 shongbee2 閱讀(579) 評論(0) 編輯收藏引用所屬分類: 數(shù)據(jù)結(jié)構(gòu)和算法

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 除法散列發(fā)解決碰撞的散列表求2-nMax的素數(shù) 用數(shù)組模擬指針和對象鏈表學習--雙向鏈表實現(xiàn) 隊列學習--數(shù)組實現(xiàn) 棧學習---數(shù)組實現(xiàn) 尋找第i小元素求最大最小值排序算法總結(jié) 希爾排序

網(wǎng)站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理