Java求质数常见几种方式-Toy模板网

这篇具有很好参考价值的文章主要介绍了Java求质数常见几种方式。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1、循环遍历

public static boolean isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    // 一定是 <= 号
    for (int i = 2; i <= Math.sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

该方法的作用是判断一个整数是否是质数（即只能被1和自身整除的正整数）。方法接收一个整数参数num，返回一个布尔值，表示num是否为质数。

方法的实现原理是使用for循环从2到num的平方根（简单思考就可以想到不需要遍历到num-1）进行遍历，判断num是否能被这个数整除。如果能被整除，说明num不是一个质数，直接返回false。如果遍历完所有可能的因子都不能被整除，说明num是一个质数，返回true。

需要注意的是，该方法对于num小于等于1的情况直接返回false，因为1不是质数。

这种方法的时间复杂度为 O(n*sqrt(n)) ，在n的值很大的时候效率较低，如果需要找出大量质数，可以用更高效的算法，另外常见的两种方法为埃氏筛法和欧拉筛法

2、埃氏筛法（埃拉托斯特尼筛法）

埃氏筛法是一种简单又历史悠久的筛法。

埃氏筛法的基本思路是先把从2开始的所有数写下来，然后从2开始，将每个质数的倍数都标记成合数，即非质数，直到筛完所有小于等于给定数n的数。这样，留下的就是小于等于n的质数。

public static List<Integer> getPrimes(int n) {

    // 为了下标和n对应，数组长度为n + 1
    boolean[] isComposite = new boolean[n + 1]; // 标记数组，false表示该下标对应的数是质数
    List<Integer> primes = new ArrayList<>(); // 用动态数组ArrayList存储质数

    for (int i = 2; i <= n; i++) {
        if (!isComposite[i]) { // 如果该数是质数
            primes.add(i); // 把该数加入质数列表
            /* 常规思路是从 i * 2 开始，但是这样会重复判断多次
               从 i * i 开始遍历，可以略过很多次判断，因为只有
               从i的平方开始才不会和前面重复，略过了与前面数字
               的公倍数
               例如i = 2时，从4开始，判断 4 6 8 10 12 14...
               当i=3时，只需要从9开始判断3的倍数，而不需要判断
               2和3的公倍数6
            */
            for (int j = i * i; j <= n; j += i) { // 标记该数的倍数为合数
                isComposite[j] = true;
            }
        }
    }

    return primes;
}

埃氏筛法时间复杂度为O(nloglogn)，此算法会重复筛，如i=2时已经判断过12，但i=3时仍然需要再次判断，增加了时间复杂度，此算法依然有优化的空间

3、欧拉筛法

欧拉筛法的基本思路是将每个数表示为质数的乘积，然后按照质数的倍数依次筛选，这样每个合数只会被筛选一次，大大减少了时间复杂度

public static List<Integer> eulerSieve(int n) {
    
    boolean[] isPrime = new boolean[n + 1]; // 标记数组，false表示该下标对应的数是质数
    List<Integer> primes = new ArrayList<>(); // 用动态数组ArrayList存储质数
    for (int i = 2; i <= n; i++) {
        if (!isPrime[i]) { // 如果该数是质数
            primes.add(i); // 就放入数组中
        }
        // 循环质数的个数次 并且不能超出范围
        for (int j = 0; j < primes.size() && i * primes.get(j) <= n; j++) {
            // i的倍数一定是合数
            isPrime[i * primes.get(j)] = true;
            // 关键 当i能整除的时候就跳出循环
            if (i % primes.get(j) == 0) {
                break;
            }
        }
    }
    // primes列表中存储的就是所有小于等于n的质数
    return primes;
}

欧拉筛法的时间复杂度是O(n)，每一个合数都被它的最小质因数筛掉文章来源地址https://www.toymoban.com/news/detail-619010.html

到了这里，关于Java求质数常见几种方式的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！