作者Leeng (老千)
看板C_and_CPP
標題Re: [問題] 判斷質數等不到所有數都除過就判定了？
時間Sun Aug 30 21:29:33 2009
整理一下
bool isPrime(int N){ //引入問題N
// 要有一些前置防呆
if( N < 2 ) return 0; // 不考慮1以下
if( N == 2 ) return 1; // 2為質數
if( N % 2 == 0 ) return 0; //偶數
//接下來才是運算部分
int M = int(sqrt(N)); //判斷N是否為質數，不需要超過根號N
for( int i = 3; i < M; i+=2 ){
if( N % i == 0 ) return 0;
}
return 1;
}
所以基本上質數判斷是(根號N)量級
另外我有試著製作質數表，就是從3開始+2往上跑，是質數就寫到txt
扣除一些初始值(2,3,5等)，判斷為質數的方法改為從txt裡面撈
(不曉得這樣跟 %(i+2)哪個比較快 )
累計到八位數就要一百多MB = =
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.238.233
※ 編輯: Leeng 來自: 61.230.238.233 (08/30 21:31)
1F：推 VictorTom:後來想到, 考慮浮點誤差, sqrt完可能還是加個0.5保險Orz 08/30 21:31
2F：推 LPH66:更好的是不用 sqrt 改成 i*i<=M 即可 08/30 21:36
3F：→ LPH66: i*i<=N 08/30 21:36
4F：→ Leeng:2F說的 在上一篇推文提出的反駁是i*i<=N在每個迴圈都要計算 08/30 21:39
5F：→ Leeng:直接給定上限只要做一次就好了 08/30 21:39
6F：→ Leeng:除非是製作大量質數表，每次N都不一樣 而要呼叫多次math.h 08/30 21:40
7F：→ Leeng:才要放棄sqrt而用i*i<=N 08/30 21:41
8F：→ Leeng:要不然就是編譯環境限制下，函數庫能省則省吧? 08/30 21:42