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+ "不是素数");
}