[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去寫而不額外建變數，
但這樣其實對效能而言可能並不一定是正面的，只是寫的時候方便
要說匿名宣告省記憶體？我覺得難說，說不定反而多耗，
或者是就算有省，那一個變數也差不了多少‧‧‧‧

[Java] 期中考

一整個很悲哀的期中考
我配到的那台電腦沒裝NetBeans
用JECrxxx那套一整個不習慣
而且還當機，寫好沒錯的程式碼就是不會動
把程式關掉重開貼上去又好了？！
浪費了我一堆時間
兩題都沒寫好，真是人生一大敗筆
不過不管怎麼說都是自己不夠熟練又不夠冷靜的問題
要改進啊....唉

第一題：用For迴圈讓程式跑出1+1+2+3+5+8.....=xxxx (加到最後一個數小於等於1000為止)

---

嗯....費式數列的變相考法
可能真的太久沒寫了，我在這題上面耍了很多寶
除了浪費了很多時間以外，最後寫出來的程式不算很漂亮
現在鞭打自己好好重寫 T__T

public class NewClass {
    public static void main(String[] args){
        int n1=0,n2=0,n3=1,sum=0;
        for(int i=0;n3<=1000;i++){
            if(i != 0){
                System.out.print("+");
            }
            System.out.print(n3);
            sum += n3;
            n1 = n2;
            n2 = n3;
            n3 = n1+n2;
        }
        System.out.print("=" + sum);
    }
}

第二題：輸入四位數西洋年判斷是否為閏年（閏年為可以被4整除，但不可被100整除，又可以被400整除）

---

題目很簡單，問題是老師很白痴。
他直接把題目從課本照抄也不先自己仔細看一下或寫一下
看看題目後面寫的閏年判斷準則，會不會詭異？
以我看到的，我會認為它是說要同時滿足可以被4與400整除，又不可被100整除。
這不用說，邏輯上就有問題直接打槍了。世界上沒有數字可以被400整除卻不能被100整除的。
我跟老師反應後他也想了老半天，還跟我說是完全沒改從課本抄來的
(這是怎樣？就算題目有錯也先推給課本嗎？)
結果被他浪費掉的時間也不還給我，害我最後寫的時間嚴重不足
其實正確的表示法應該要把「又可以被400整除」，改成「除非它也可以被400整除」
拜托....身為台灣人，這樣才是正確的中文表達方法好嗎
好啦，在正確的表達後不難看出條件
程式碼如下：

import java.io.*;
public class NewClass1 {
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int in_y;
        System.out.print("請輸入四位數西洋年：");
        in_y = Integer.parseInt(in.readLine());
        if((in_y%4==0 &&in_y%100!=0)||(in_y%100==0&&in_y%400==0)){
            System.out.print(in_y + "為閏年");
        }else{
            System.out.print(in_y + "不是閏年");
        }
    }
}