是技術，更是藝術

一心編程，就沒有解決不了的問題

posts - 9, comments - 11, trackbacks - 0, articles - 0

快速判斷素數算法

Posted on 2010-07-16 21:40 李熙建閱讀(4238) 評論(3) 編輯收藏引用所屬分類: 算法

引理：如果 a 是一個大于1的整數，而所有小于或等于根號 a 的素數都除不盡 a ，則 a 是素數。
理想的判斷素數的方法應該是將所有小于或等于根號n的素數去除n，但是n是一個隨機大于1的整數，小于這個數的平方根的素數表不好給定。下面介紹的方法，本意是動態的構建素數表，但是引入了很多冗余的除數。

代碼：

bool prime (int num)

{

if (num == 2 || num == 3 || num == 5)

return true;

if (num % 2 == 0 || num % 3 == 0 || num % 5 == 0 || num == 1)

return false;

unsigned long c = 7;

int maxc = int (sqrt (num));

while (c <= maxc)

{

if (num % c == 0)

return false;

c += 4;

if (num % c == 0)

return false;

c += 2;

if (num % c == 0)

return false;

c += 4;

if (num % c == 0)

return false;

c += 2;

if (num % c == 0)

return false;

c += 4;

if (num % c == 0)

return false;

c += 6;

if (num % c == 0)

return false;

c += 2;

if (num % c == 0)

return false;

c += 6;

}

return true;

}

分析：
　　相對于sqrt(n)次除，上面的程序需要sqrt(n)*8/30次除，效率提升了15/4倍。
　　自然數n，我們假設小于n的素數數F(n),F(n)的分布規律為：當n趨向于無窮大時，F(n)/(x/logx) = 1;
所以，動態的冗余度近似為：(sqrt(n)*4/15-x/logx)/sqrt(n)*4/15

其他更好的判斷素數的算法，希望你能給我留言或者寫在評論上，謝謝！

Feedback

# re: 快速判斷素數算法回復 更多評論

2011-06-02 20:47 by 某W

這方法很強大~
謝謝~

# re: 快速判斷素數算法回復 更多評論

2011-08-01 09:19 by 李熙建

@某W
謝謝，拋磚引玉而已，期待你提出更優秀的方法

# re: 快速判斷素數算法 回復 更多評論

2012-10-25 19:21 by aa

理論依據是什么？

刷新評論列表

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

相關文章: 求數組子數組之和的最大值和子數組位置快速判斷素數算法時間統計的幾種方法

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

是技術，更是藝術

導航

常用鏈接

留言簿

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

快速判斷素數算法

Feedback

# re: 快速判斷素數算法回復 更多評論

# re: 快速判斷素數算法回復 更多評論

# re: 快速判斷素數算法 回復 更多評論

是技術，更是藝術

導航

常用鏈接

留言簿

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

快速判斷素數算法

Feedback

# re: 快速判斷素數算法 回復 更多評論

# re: 快速判斷素數算法 回復 更多評論

# re: 快速判斷素數算法 回復 更多評論

# re: 快速判斷素數算法回復更多評論

# re: 快速判斷素數算法回復更多評論

# re: 快速判斷素數算法回復更多評論