CIYAWASAY

這個程式可以找出從1到某數範圍內的質數
我和swanky寫的 (swanky:pair programming)
改過後效率還不錯 從1~100000的範圍 大概花了2.157秒
不過也可能是這機器還不賴
大家也可以自己試試看^^~

質數的定義:除了1之外的自然數只能被1或自己整除的數

方法是從2開始找到質數後存入一個陣列
以後的數都拿之前找到的質數來判斷是否整除
除數的範圍就是質數的第一個到比被除數開根號小的質數

ex:要判斷12是不是質數 先開根號取整數+1得4
用找到的質數去除 就是除以2和3結果整除 所以不是質數
但其實只除以2就判斷出他不是質數了

public class DetectPrime{
   public static void main(String[] args){
      long before = System.currentTimeMillis();
      int number = 100;
      if(args.length == 1){
         try{
            number = Integer.parseInt(args[0]);
         }catch(Exception e){
            System.err.println(e);
         }
      }
      int[] primes = new int[number];
      primes[0] = 2;
      int count = 0;
      
      for(int i = 2; i < number; i++){
         
         boolean prime = true;
         int max = (int)Math.sqrt(i) + 1;
         
         for(int j = 0; primes[j] < max; j++){
            if((i % primes[j]) == 0){
               prime = false;
               break;
            }
         }
         
         if((i == 0)||(i == 1)) continue;
         if(prime){
            primes[count] = i;
            System.out.println(i);
            count++;
         }
      }
      long after = System.currentTimeMillis();
      System.out.print("1~" + number + "有" + count +"個質數");
      System.out.print("共花了" + (after-before) + "milliseconds");
   }
}

# posted by Unknown @ 08:36