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