Java中查找给定数字下最大素数的2种方法

寻找小于给定数的最大素数是计算机科学和数学中的一个经典问题。

在这个简短的教程中，我们将探讨在 Java 中解决此问题的两种方法。

1、使用暴力
让我们从最直接的方法开始。我们可以通过从给定数向后迭代直到找到一个素数来找到给定数下的最大素数。对于每个数字，我们通过验证它不能被除 1 之外的任何小于自身的数字整除来检查它是否是质数：

public static int findByBruteForce(int n) {
    for (int i = n - 1; i >= 2; i--) {
        if (isPrime(i)) {
            return i;
        }
    }
    return -1; // Return -1 if no prime number is found
}
public static boolean isPrime(int number) {
    for (int i = 2; i <= Math.sqrt(number); i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

isPrime()方法的时间复杂度 是 O(√N)，我们可能需要检查最多n 个数字。因此，该解决方案的时间复杂度为 O(N √N)。

2、使用埃拉托色尼筛选算法
查找给定数字下最高有效素数的更有效方法是使用埃拉托色尼筛法算法。该算法有效地考虑给定限制内的所有素数。一旦我们有了所有素数，我们就可以轻松找到小于给定数的最大素数：

public static int findBySieveOfEratosthenes(int n) {
    boolean[] isPrime = new boolean[n];
    Arrays.fill(isPrime, true);
    for (int p = 2; p*p < n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i < n; i += p) {
                isPrime[i] = false;
            }
        }
    }
    for (int i = n - 1; i >= 2; i--) {
        if (isPrime[i]) {
            return i;
        }
    }
    return -1;
}

这次，我们在第一个解决方案中使用相同的isPrime()方法。我们的代码遵循三个基本步骤：
  • 初始化一个布尔数组isPrime[]来跟踪n以内的数字的素数状态，默认为true。
  • 对于每个素数p ，将其从p*p到n的倍数标记为非素数(false)。这可以有效地过滤掉非素数。
  • 从n-1向后迭代以找到标记为true的最高索引。

埃拉托斯特尼筛法的时间复杂度为 O(N log (log (N))) ，这比大n的强力方法要高效得多。