Re: [問題] 判斷質數等不到所有數都除過就判定了？

[Leeng (老千)]

整理一下

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)
推 VictorTom:後來想到, 考慮浮點誤差, sqrt完可能還是加個0.5保險Orz
推 LPH66:更好的是不用 sqrt  改成 i*i<=M 即可
→ LPH66:                        i*i<=N
→ Leeng:2F說的 在上一篇推文提出的反駁是i*i<=N在每個迴圈都要計算
→ Leeng:直接給定上限只要做一次就好了
→ Leeng:除非是製作大量質數表，每次N都不一樣 而要呼叫多次math.h
→ Leeng:才要放棄sqrt而用i*i<=N
→ Leeng:要不然就是編譯環境限制下，函數庫能省則省吧?