JAVA判断一个数是否是质数/批量求质数

1.质数定义：

只能被1或者自身整除的自然数（不包括1），称为质数。

2.判断一个数是否是质数

方法一：根据质数的定义求(效率最低)

利用它的定义可以循环判断该数除以比它小的每个自然数（大于1），如果有能被它整除的，则它就不是质数。 时间复杂度：$O(n^2)$

/**
     * 判断传入数值是否为素数
     * @param num
     * @return flag
     */
    private static boolean isPrime1(int num){
        boolean flag=true;              //判断是否为质数的标记
        for (int j=num-1;j>1;j--){   //逐个除以[1,n]区间的数字
            if (num%j==0){
                flag = false;           //若能整除，则置false标记为合数
            }
        }
        return flag;
    }

方法二：利用合数定理（原理和方法一一致,效率提高了）

如果一个数是合数，那么它的最小质因数肯定小于等于他的平方根。

例如，20的最小质因数4必然小于20开方。

时间复杂度：$O(n^{\frac{1}{2}})$

/**
     * 方法二
     * @param num
     * @return
     */
    private static boolean isPrime2(int num){
        int s = (int) Math.sqrt(num);     //求出数字n的开方
        boolean flag = true;            //判断是否为质数的标记
        for (int j=2;j<=s;j++){            //逐个除以[1,n^1/2]区间的数字
            if (num % j == 0){
                flag = false;            //若能整除，则置false标记为合数
            }
        }
        return flag;
    }

3.批量求质数--筛法求质数（效率最高，但会比较浪费内存）

首先建立一个boolean类型的数组，用来存储你要判断某个范围内自然数中的质数.
例：
你要输出小于100的质数，可以建立一个大小为101（建立11个存储位置是为了让数组位置与其大小相同）的
boolean数组，位置1置false，其他位置初始化为true。
即数组初始状态 [null,false,true,true......]

然后再获取数字n的开方，即10，然后再从2开始，2的倍数位置置false,即 4 6 8 10....，
3的倍数位置置false即 6 9 12..........,以此类推，就把初始数列的合数位置值变成false，true值的位置则为素数。

/**
     * 通过对数组进行标记后，再逐个判断
     * @param num
     * @return
     */
    private static boolean [] isPrime3(int num){
        boolean [] array = new boolean[num+1];  //加1为了数组位置一致
        array[1] = false;                       //false为合数，ture为质数    1不是质数
        for (int i = 2;i < num;i++){
            array[i] = true;                    //生成一个长度为n的布尔数列 [null,false,true........]
        }
        int s = (int)Math.sqrt(num);
        for (int i = 2;i<=s;i++){
            if (array[i]){                      //检查是否已经置fales（可以防止重复置false）
                for (int j=i;j*i<=num;j++){      //将i的倍数下标位置置为false
                    array[j*i] = false;
                }
            }
        }
        return array;                           //标记好后的数组返回
    }