[Java]如何列出100以下的所有質數

程式語言另一個常見的作業就是跟質數當朋友
來找找一個數是不是質數，或找出100以內所有的質數這種題目


今天談談怎麼找出1到100的所有質數吧
解決這個問題前先處理下面兩個問題
如何印出2到100(最小的質數是2)，答案我想剛學過迴圈的應該都做的出來，就是

  for(int i=2;i<=100;i++){
   System.out.println(i);
  }

接下來只要把1到100每個數都檢查他是不是質數就可以了，如何檢查一個整數不是質數呢
首先質數的定義是大於一的整數，除了1跟自己本身以外，沒有其他因數。
所以呢最簡單的想法就是設一個boolean去處理他
舉個例子好了，檢查7是否為質數

  boolean isPrime;
  for(int i=2;i<7;i++){

   if(7%i==0){
    isPrime=false;
   
   }
  }

所以這個迴圈就會檢查二以上，比7小的數字有沒有整除他，有整除表示7有其他因數 就不是質數囉，當然最後因為2到6並不會整除7，最後isPrime的值就會是true，所以就可以抓出7是質數。

有了上述兩件事我們就可以開始把兩個程式合併起來

  boolean isPrime;
  
  for(int i=2;i<=100;i++){
   isPrime=true;
   
   for(int j=2;j<i;j++){

    if(i%j==0){
     isPrime=false;
    
    }
   }
   
   if(isPrime){
    System.out.print(i+" ");
    
   }
   
  }

 }

注意兩個迴圈不太一樣，第一個迴圈是<=100，因為你檢查的時候要檢查的是2到100
但是第二個迴圈要檢查的時候不能檢查自己，因為自己一定被自己整除，
弄成小於等於的話不管怎樣isPrime一定會false，那些該用小於等於，那些東西該用小於;，必須想的很清楚，不然程式就會花式秀bug，你還不知道怎麼死的

做到這看似完成了，但是其實這個方法從2檢查到100大概要做快5000次
(第二個for迴圈執行了4851次)
並不是很有效率，事實上你檢查的時候如果不是質數並不會用繼續檢查其他數字，可以將迴圈做break跳出，另外，在數學的觀點來講，X這個整數如果你檢查到根號X都沒有質因數，他就是質數了，故程式碼可以改成

  boolean isPrime;
  
  for(int i=2;i<=100;i++){
   isPrime=true;
   
   for(int j=2;j<Math.sqrt(i);j++){

    if(i%j==0){
     isPrime=false;
     break;
    }
   }
   
   if(isPrime){
    System.out.print(i+" ");
    
   }
   
  }

到了這邊第二個for迴圈的進入次數就被壓縮到剩下232次，應該可以感受到用不同的方法去實做程式，不去想辦法降低程式運算次數，只靠靠硬體硬做效能會有多大的差距了。
我解出上述答案後過了幾天我就在思考，如果我只檢查比根號x小的所有質數，會不會更快呢？於是我寫出了下面的class

public class ShowPrime {



 public static void main(String[] args) {

  showPrime(100); 

 

 }



 



 

 public static void showPrime(int k){

  int[] prime = new int[(k+1)/2];  

  prime[0] = 2;//the first prime is 2

  int pCount=0;

  int count=0;

  boolean isPrime=true;

  for(int i=2;i<=k;i++){

   

   isPrime=true;

   for(int j=0;prime[j]<=Math.sqrt(i);j++){

    

    if(i%prime[j]==0){

     isPrime=false;

     break;

    }

   }

   if(isPrime){

    prime[pCount]=i;

    pCount++;

    System.out.print(i+"\t");

    count++;

    if(count%10==0){//create new line per 10 numbers

     System.out.println("");

    }

      

   }

     

  }

  

 }

 

}

這邊會另外需要記憶體去儲存質數，所以在100的時候我不覺得這個方法會比較好，但是在數字更大的時候這個方法執行效能應該就會比較好了


最後提一下，我認為這邊的方法並不是最快速的方法，但是初學程式的新手最需要學習的概念，並不是只是程式語法本身，語法很重要，不去學會你完全不能開始寫程式，但是解決問題的方法也是另一個重要課題，學習如何依照使用者的要求，去找出解決問題的方案，並且找出解決方案後，去思考能不能改善他的效能，所以這個問題除了把答案解出來以外，試著去思考如何撿少運算次數一定有幫助的