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 编程语言检查最近素数的不同方法。