Find the Largest Prime Under the Given Number in Java

1. 概述

在计算机科学和数学中，找到给定数以下的最大质数是一个经典问题。在这个简短教程中，我们将探讨两种用Java解决这个问题的方法。

2. 使用暴力搜索

让我们从最直接的方法开始。我们可以通过从给定的数开始向前遍历，直到找到一个质数。对于每个数，我们检查它是否是质数，即验证它除以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)**。

3. 使用埃拉托斯特尼筛法

寻找给定数以下的最大质数的一个更有效的方法是使用埃拉托斯特尼筛法。此算法有效地考虑了给定限制内的所有质数。一旦我们有了所有的质数，就可以很容易地找到给定数以下的最大质数：

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()方法。我们的代码遵循三个基本步骤：

1. 初始化一个布尔数组isPrime[]，用于跟踪从1到n的数字的质数状态，默认值为true。
2. 对于每个质数p，从pp到n*标记其倍数为非质数（false）。这有效地过滤掉非质数。
3. 从n-1开始向后遍历，找到最高索引标记为true的数。

**埃拉托斯特尼筛法的时间复杂度为O(N log (log (N)))*，对于大数n*来说，比暴力搜索方法更高效。

4. 总结

在这篇教程中，我们探讨了两种在Java中找到给定数以下最大质数的方法。暴力搜索方法更为直观但效率较低。埃拉托斯特尼筛法提供了一个时间复杂度为O(n log log n)的更高效解决方案，对于较大的数来说，它是首选。

本文示例代码可在GitHub上找到。