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. 初始化一個boolean數組isPrime[]來追蹤n以內的數字的質數狀態，預設為true 。
2. 對於每個質數p ，將其從p*p到n的倍數標記為非質數(false) 。這可以有效地過濾掉非素數。
3. 從n-1向後迭代以找到標記為true的最高索引。

埃拉托斯特尼篩法的時間複雜度為 O(N log (log (N))) ，這比大n的強力方法要高效得多。

4。結論

在本教程中，我們探索了兩種在 Java 中尋找給定數字下最大素數的方法。蠻力法較直接，但效率較低。埃拉托斯特尼篩法提供了一種更有效的解決方案，時間複雜度為 O(n log log n)，使其成為更重要數字的首選。

本文中的範例程式碼可以在 GitHub 上找到。