java素數（質數）

素數概念

素數又叫質數。素數，指的是“大于1的整數中，隻能被1和這個數本身  整除的數”。

20以内的素數：2、3、5、7、11、13、17、19.   最小的素數是2，1既不是素數也不是合數。

​​什麼是素數？ (baidu.com)​​

合數的概念：大于1的整數中，除了1和自身外，還能被其他正整數整除的數。也可表述為：在大于1的整數中，除了1和自身兩個約數外，還有其他約數的正整數。

1、判斷1~100之内有多少素數，并将素數列印出來。

方法1：從 2 到 n-1 周遊每個數字是否可以整除

import java.util.ArrayList;
import java.util.List;

public class SushuJudge {
    public static void main(String[] args) {
        List list = new ArrayList();
        for (int i = 1; i <= 100; i++) {
            if(isPrime(i)){
                list.add(i);
                System.out.println(i);
            }
        }

        System.out.println("總共有："+list.size()+"個素數");
     }

    // 判斷是否是素數
    private static boolean isPrime(int i){
        boolean flag = true;
        for (int j = 2; j < i; j++) {
            if(i%j==0){
                flag=false;
                break;
            }
        }
        return flag;
    }
    
    /**
    //1-100之間的質數--------2
    public static void isPrime(String[] args) { 
        for(int i=2;i<=100;i++) {   
            for(int j=2;j<=i;j++) {
                if(i%j==0 && i!=j) {
                    break;     
                }
                if(j==i) {
                    System.out.println("質數：i= "+i);     
                }    
            }
        }
    }
    */

}      

方法2：去掉偶數後，從 3 到 x-1, 每次加 2

if(x ==1 || x %2 ==0 && x !=2 ) {
    isPrime = false;
    
}else {
    for(int i =2; i<x; i +=2) {
        if( x % i == 0) {
            isPrime = false;
            break;
        }
    }
}
if( isPrime) {
    System.out.println(x +"是素數");  
}else {
    System.out.println(x+ "不是素數");
}      

方法3：從 2 到 n/2 循環周遊

将循環範圍定在2到指定數的二分之一（原理：任何一個數的最大因數都小于等于它的二分之一，是以隻要從2查找到，如果都沒有被整除就是素數，因為到這裡已經查找到他的最大因數了。例如24的最大因數為12，100的最大因數為50.）這樣就會減少循環次數。

public static void isPrime2(int x){
        boolean flag = true;
        int i=0;
        int j=0;
        // 從 2 到 n/2  循環周遊
        for(j=2;j<=x/2;j++){
            if(x%j==0){
                flag=false;
                break;
            }
        }
        if(flag==true){
            System.out.println("是素數");
        }else{
            System.out.println("不是素數");
        }
    }      

方法4：從 2 到 根号n 循環周遊

其實隻要把循環一直從 2 嘗試到 根号x   {Math.sqrt(x)}就可以，不難發現，一個數的兩個因數中，畢然有一個小于等于根号x，一個大于等于根号x

if(x ==1 || x %2 ==0 && x !=2 ){
    isPrime = false;
}else {
    //for( int i =2; i*i<=x; i++){
    for( int i =2; i<= Math.sqrt(x); i+){
        if( x % i == 0){
            isPrime = false;
            break;
        }
    }
}

if( isPrime) {
    System.out.println(x +"是素數");   
}else {
    System.out.println(x+ "不是素數");
}