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

jupiter
2022-04-05 / 7 评论 / 1,206 阅读 / 正在检测是否收录...
温馨提示:
本文最后更新于2022年04月05日,已超过945天没有更新,若内容或图片失效,请留言反馈。

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;                           //标记好后的数组返回
    }
0

评论 (7)

打卡
取消
  1. 头像
    jupiter 作者
    Windows 10 · Google Chrome

    CommentToMail插件测试

    回复
    1. 头像
      jupiter 作者
      Windows 10 · Google Chrome
      @ jupiter

      CommentToMail插件测试

      回复
  2. 头像
    LY
    Windows 10 · Google Chrome

    CommentToMail插件测试

    回复
    1. 头像
      jupiter 作者
      Windows 10 · Google Chrome
      @ LY

      CommentToMail插件测试

      回复
  3. 头像
    jupiter 作者
    Windows 10 · Google Chrome

    CommentToMail插件测试

    回复
    1. 头像
      jupiter 作者
      Windows 10 · Google Chrome
      @ jupiter

      CommentToMail插件测试

      回复
  4. 头像
    jupiter 作者
    Windows 10 · Google Chrome

    CommentToMail插件测试

    回复