C++研究

Ｃ++細節深度探索及軟件工程

:: 管理 ::

37 隨筆 :: 0 文章 :: 74 評論 :: 0 Trackbacks

How can you efficeny judge whether the num is primer?

A friend ask me 'How can you efficeny judge whether the num is primer? '

There is a easy way to do it , the follow code isn't written by me but a classic method

E.G quote from STL tutorial reference

#include <iostream>

#include <list>

#include <algorithm>

#include <cstdlib> //for abs()

using namespace std;

//predicate, which returns whether an integer is a prime number

bool isPrime (int number)

{

//ignore negative sign

number = abs(number);

// 0 and 1 are prime numbers

if (number == 0 || number == 1) {

return true;

}

//find divisor that divides without a remainder

int divisor;

for (divisor = number/2; number%divisor != 0; --divisor) {

;

}

//if no divisor greater than 1 is found, it is a prime number

return divisor == 1;

}

posted on 2007-04-19 02:39 常興龍閱讀(347) 評論(1) 編輯收藏引用所屬分類: Algorithm

我的看法：
（1）0和1都不算素數。
（2）2和3都是素數，可以直接返回。
（3）判斷一個比較小的數（可以認為在long范圍內的吧，如果是1024二進制位的大數就得想別的辦法了）是不是素數肯定得窮舉，提高效率就得根據已知的條件縮小窮舉的空間。我認為以上程序的窮舉空間還不夠小。
其實只要對大于3的數num窮舉從2～sqrt(num)就夠了，而不用擴展到num/2。假如判斷1122是不是素數，只需要窮舉1122對2~33這個范圍的余數有沒有為0的就可以，超過33的數，如果正好有另一個積數，那么這個積數一定小于sqrt(num)，乘法運算是對稱的，這是數實際上已經窮舉過了。這樣以1122為例就少窮舉了528次，效率提高了約17倍，而這個num越大，效率提高就越明顯。

不知道我說的對不對，請大家指教啊。
回復更多評論

刷新評論列表

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


相關文章: 求有序序列公共部分(集合交集的O(n)復雜度求法) 精煉循環右移 Some algorithms about judging a prime . How can you efficeny judge whether the num is primer?

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

>　hi的博客

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

C++研究

公告

常用鏈接

留言簿(8)

隨筆分類(19)

隨筆檔案(37)

相冊

收藏夾

好友連接

學術算法研究

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

評論