1. Overview
1.概述
Finding the largest prime less than a given number is a classic problem in computer science and mathematics.
查找小于给定数字的最大 prime 是计算机科学和数学中的一个经典问题。
In this short tutorial, we’ll explore two approaches to solve this problem in Java.
在这个简短的教程中，我们将探讨用 Java 解决这个问题的两种方法。
2. Use Brute Force
2.使用蛮力
Let’s begin with the most straightforward way. We can find the largest prime under a given number by iterating backward from the given number until we find a prime. For each number, we check if it’s prime by verifying that it’s not divisible by any number less than itself except 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;
}The time complexity of the isPrime() method is O(√N), and we might need to check up to n numbers. Thus, the time complexity of this solution is O(N √N).
isPrime() 方法的时间复杂度为 O(√N)，而我们可能需要检查多达 n 个数字。因此，此解决方案的时间复杂度为 O(N √N)。
3. Use Sieve of Eratosthenes Algorithm
3.使用埃拉托塞尼斯筛算法
A more efficient way to find the most significant prime number under a given number is using the Sieve of Eratosthenes algorithm. This algorithm efficiently considers all prime numbers up to a given limit. Once we have all prime numbers, we can easily find the largest prime less than the given number:
使用 Sieve of Eratosthenes 算法可以更有效地找出给定数字下最重要的质数。该算法可以有效地考虑给定极限以内的所有质数。一旦我们得到了所有质数，我们就可以很容易地找到小于给定数的最大质数：
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;
}This time, we use the same isPrime() method in the first solution. Our code follows three basic steps:
这次，我们使用与第一个解决方案相同的 isPrime() 方法。我们的代码遵循三个基本步骤：
- Initialize a boolean array isPrime[] to track prime status for numbers up to n, defaulting to true.
- For each prime p, mark its multiples as non-prime (false) starting from p*p to n. This efficiently filters out non-prime numbers.
- Iterate backward from n-1 to find the highest index marked true.
The time complexity of the Sieve of Eratosthenes is O(N log (log (N))), which is much more efficient than the brute force approach for large n.
埃拉托斯特尼筛法的时间复杂度为 O(N log (log (N)))，对于大n来说，这比蛮力法要有效得多。
4. Conclusion
4.结论
In this tutorial, we’ve explored two ways to find the largest prime in Java under the given number. The brute force method is more straightforward but less efficient. The Sieve of Eratosthenes offers a more efficient solution with a time complexity of O(n log log n), making it the preferred choice for more significant numbers.
在本教程中，我们探讨了用 Java 找出给定数字下最大质数的两种方法。蛮力法更直接，但效率较低。埃拉托塞尼斯筛法提供了一种更高效的解决方案，其时间复杂度为 O(n log log n)，因此它是较大数字的首选。
The example code from this article can be found over on GitHub.