C++研究

Ｃ++細(xì)節(jié)深度探索及軟件工程

:: 管理 ::

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 常興龍閱讀(346) 評論(1) 編輯收藏引用所屬分類: Algorithm

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

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

刷新評論列表

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


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

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

>　hi的博客

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

C++研究

公告

常用鏈接

留言簿(8)

隨筆分類(19)

隨筆檔案(37)

相冊

收藏夾

好友連接

學(xué)術(shù)算法研究

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

評論