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