Java 最近素數程式

---

素數是一個大於 1 的正整數，它只能被 1 和它本身整除。素數是數學和計算機科學中的一個基本概念。它們是隻能被 1 和自身整除的整數。

在許多演算法中，查詢素數是一項重要的任務，並且有幾種方法可以確定一個數是否為素數。其中一個問題是找到給定數字最接近的素數。

問題陳述

對於給定的數字，使用Java 程式語言找到最接近的素數。考慮以下示例 -

輸入

54

輸出

53 is the closest prime number to 54.

查詢最近素數的不同方法

我們提供了不同的方法來解決這個問題。

• 使用蠻力法
• 使用篩法

使用蠻力法查詢最近素數

在這種方法中，程式將初始化一個整數。然後使用蠻力法找到最接近的素數。

蠻力法的演算法

• 步驟 1：檢查輸入數字是否為素數。
• 步驟 2：如果輸入數字是素數，程式列印該數字並退出。
• 步驟 3：如果輸入數字不是素數，程式透過檢查輸入數字之前和之後的數字來查詢最接近的素數。
• 步驟 4：使用蠻力法透過檢查直到其平方根的所有數字來檢查一個數字是否為素數。
• 步驟 5：列印輸入數字最接近的素數。

示例

public class Main {
   // Function to check if a number is prime
   static boolean isPrime(int n) {
      if (n <= 1) return false;
      for (int i = 2; i <= Math.sqrt(n); i++) {
         if (n % i == 0) return false;
      }
      return true;
   }
   public static void main(String[] args) {
      int n = 54;
      // Check if the input number is prime
      if (isPrime(n)) {
         System.out.println(n + " is a prime number.");
         return;
      }
      // Find the closest prime number by checking numbers above and below the input number
      int lower = n - 1;
      int upper = n + 1;
      while (true) {
         if (isPrime(lower)) {
            System.out.println(lower + " is the closest prime number to " + n + ".");
            return;
         } else if (isPrime(upper)) {
            System.out.println(upper + " is the closest prime number to " + n + ".");
            return;
         }
         lower--;
         upper++;
      }
   }
}

輸出

53 is the closest prime number to 54.

使用篩法查詢最近素數

在這種方法中，程式將初始化一個整數。然後使用篩法生成素數列表，然後找到最接近的素數。

篩法的演算法

• 步驟 1：使用篩法生成直到 2n 的素數列表。
• 步驟 2：查詢輸入數字最接近的素數。
• 步驟 3：使用篩法透過消除每個素數直到其平方根的所有倍數來生成素數列表。
• 步驟 4：透過檢查素數列表中輸入數字上方和下方的數字來查詢最接近的素數。
• 步驟 5：列印輸入數字最接近的素數。

示例

import java.util.Arrays;
public class Main {
   // Function to generate a list of prime numbers up to a given limit
   static boolean[] sieve(int limit) {
      boolean[] prime = new boolean[limit+1];
      Arrays.fill(prime, true);
      prime[0] = false;
      prime[1] = false;
      for (int i = 2; i*i <= limit; i++) {
         if (prime[i]) {
            for (int j = i*i; j <= limit; j += i) {
               prime[j] = false;
            }
         }
      }
      return prime;
   }
   // Function to find the closest prime number to a given number
   static int closestPrime(int n, boolean[] prime) {
      int lower = n - 1;
      int upper = n + 1;
      while (true) {
         if (lower >= 0 && prime[lower]) {
            return lower;
         } else if (upper < prime.length && prime[upper]) {
            return upper;
         }
         lower--;
         upper++;
      }
   }
   public static void main(String[] args) {
      int n = 27;
      // Generate a list of prime numbers up to 2n
      boolean[] prime = sieve(2*n);
      // Find the closest prime number to n
      int closest = closestPrime(n, prime);
      System.out.println("The closest prime number to " + n + " is " + closest);
   }
}

輸出

The closest prime number to 27 is 29

在本文中，我們探討了使用 Java 程式語言檢查最近素數的不同方法。