[Java] 計算質數的效率

計算質數的題目應該是每個人程式入門都會碰到的
當然這個題目以現今的電腦來說應該沒有什麼效率的問題
只是前陣子因為上了學校很弱的Java課，寫到這種題目
突然又想來實驗一下，小小的寫法差異會帶來怎樣的效率差別？
一般常見的的思考方法是用for迴圈，起始為除數2，一直除到N-1為止
簡單的程式碼會如下：

for(int i=0;i<=N-1;i++){
    if(N % i ==0){
        xxxx;
    }
}

我之前有想過，如果當N很大時，迴圈一直run到N-1豈不很費時？
因為最小的除數是2，換句話說最大的除數一定不會大於N除以2
例：假設N是100，100最大的除數就是100/2的50，
而如果N是99，最大的除數也不可能超過99/2
如果是這樣的情況，當N是質數時，可以少跑一半的迴圈
不過後來我去查了一下資料，其實/2的想法還不夠聰明 XD
最直接的方法是除到把N開根號為止
因為超過根號N之後可能的除數就皆已出現過
以下就是實作看看執行時間上的差異，用迴圈跑求65537是否是質數跑五千次
首先是用N-1方法跑：

---

public class Test {
    public static void main(String[] args) {
        boolean ans = true;
        long in_num = 65537;
        long time1, time2;
        time1 = System.currentTimeMillis();
        for (int k = 0; k <= 5000; k++) {
            for (long i = 2; i <= in_num - 1; i++) {
                if (in_num % i == 0) {
                    ans = false;
                    break;
                }
            }
            if (ans) {
                //System.out.println("是質數");
            }
        }
        time2 = System.currentTimeMillis();
        System.out.println((double) (time2 - time1) / 1000);
    }
}

N-1的版本跑五千次總共花了24.312秒（數據皆以公司爛爛的老賽揚上跑的）
那再來就是根號N的版本

---

public class Test {
    public static void main(String[] args) {
        boolean ans = true;
        long in_num = 65537;
        long time1, time2;
        time1 = System.currentTimeMillis();
        for (int k = 0; k <= 5000; k++) {
            for (long i = 2; i <= Math.pow(in_num, 0.5); i++) {
                if (in_num % i == 0) {
                    ans = false;
                    break;
                }
            }
            if (ans) {
                //System.out.println("是質數");
            }
        }
        time2 = System.currentTimeMillis();
        System.out.println((double) (time2 - time1) / 1000);
    }
}

利用Java的Math.pow去求出根號N
這個版本只跑了1.329秒
雖然比N-1快上了18.2倍，但是根號N法好像也沒有想像的快？
因為測驗的N越大，根號N法的優勢就越大
當我們把N換成比較小的質數1937跑五萬次時，根號N法跑了0.516秒
而N-1法卻只跑了0.063秒，N-1法反倒快了8.1倍
這樣的結果還令人覺得滿吃驚的
這邊我想到一個問題，會不會是因為For判斷式中的Math.pow每次都要重新計算呢？
於是我將開根號的動作另外用一個變數先存，變數的宣告與賦值都包含在計時範圍內
結果這個版本的根號N只花了0.015秒，成功的在小質數上也勝過了N-1
於是我們再回頭去實驗三種情況的大質數，結果出爐
N=65537，圈數五千。N-1法：24.312秒，根號N法：1.329秒，新根號N法：0.094秒

---

結論：使用迴圈時常習慣判斷式用function去寫而不額外建變數，
但這樣其實對效能而言可能並不一定是正面的，只是寫的時候方便
要說匿名宣告省記憶體？我覺得難說，說不定反而多耗，
或者是就算有省，那一個變數也差不了多少‧‧‧‧