隨感而發

雜七雜八

隨筆分類(62)

隨筆檔案(67)

統計

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

留言簿(13)

閱讀排行榜

評論排行榜

求2-nMax的素數

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

#include <stdio.h>

#include <stdlib.h>

int g_nPrime[100000];

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

//返回素數的個數

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

{

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

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

{

return 0;

}

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

nPrime[0] = 2;

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

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

{

int j;

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

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

{

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

{

break;

}

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

{

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

++nNumber;

}

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

{

//如果該數位最大下標對應值的平方，最大下標加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;

}

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

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

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

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

posted on 2009-05-04 19:42 shongbee2 閱讀(593) 評論(0) 編輯收藏引用所屬分類: 數據結構和算法

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

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

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品