爬
qq：286402937 架構-開源交流 167813458 lomox群：41830909 https://github.com/caidongyun

求素數時間測試

/*

求素數

1000W以內的素數，27063ms

100W以內的素數，1141ms

10W以內的素數，47ms

by蔡東赟于無聊的09.09.22日

*/

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<assert.h>

#include<ctime>

#include<cmath>

using namespace std;

const int MAX = 10000000;

int findvalue[MAX] = {2};

int find = 1;

bool IsPrim(int value)

{

assert(value >= 2);

int flag = (int) sqrt((double)value);

if(value == 2)

return true;

for (int i = 0; i < find && i <= flag; i++)

{

if( (value % findvalue[i]) == 0)

{

return false;

}

findvalue[find++] = value;

return true;

}

int main()

{

double start,finish;

start = clock();

for (int j = 3;j < MAX; j++)

{

if (IsPrim(j))

{

//cout << "" << j << endl;

}

finish = clock();

cout << "time:" << (finish - start) << "ms" <<endl;

system("pause");

return 0;

}

posted on 2009-09-22 10:38 爬閱讀(1736) 評論(7) 編輯收藏引用所屬分類: algorithm

評論:

# re: 求素數時間測試 2009-09-22 11:47 | abettor

將已經求出的素數放入一個數組，判斷下一個數是否為素數時，讓他去除當前已經得出的所有素數。回復更多評論

# re: 求素數時間測試 2009-09-22 13:18 | 戴爾電腦

不錯啊！！！回復更多評論

# re: 求素數時間測試 2009-09-22 15:34 | cqh

暈爺還寫這個啊，看來是在鞏固基礎，加油！回復更多評論

# re: 求素數時間測試[未登錄] 2009-09-23 16:30 | vincent

orz..用篩選法吧回復更多評論

# re: 求素數時間測試 2009-09-23 19:25 | cdy20

@cqh
我在練規范 - - ！！回復更多評論

# re: 求素數時間測試 2009-09-23 21:43 | cdy20

@vincent
不是回復更多評論

# re: 求素數時間測試 2009-09-23 21:44 | cdy20

@abettor
是回復更多評論

刷新評論列表

只有注冊用戶登錄后才能發表評論。


相關文章: zlib算法（暫存，壓縮解壓）曬掉論文《BP神經網絡的異常點檢測應用可行性研究》 O(n)時間O(1)輔助空間，循環移位求素數時間測試 hdu Northcott Game 尼姆博奕 (Nimm Game) 威佐夫博奕(Wythoff Game) 圖算法進度

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