Java 寻找最接近的质数

质数是大于1的正整数，只能被1和它本身整除。

质数是数学和计算机科学中的基本概念。它们是只能被1和本身整除的整数。在许多算法中，找到质数是一项重要任务，有几种方法可以确定一个数是否为质数。其中一个问题是找到给定数最接近的质数。

在这里，我们将探讨如何找到任意数的最接近的质数。

让我们开始吧！

例如

给定整数：15

最接近的质数：13

步骤

步骤-1

步骤1 ：检查输入数是否为质数。

步骤2 ：如果输入数是质数，程序会输出该数并退出。

步骤3 ：如果输入数不是质数，则程序会通过检查输入数前后的数来寻找最接近的质数。

步骤4 ：使用蛮力法来检查一个数是否为质数，通过检查所有小于它平方根的数。

步骤5 ：打印输入数最接近的质数。

步骤-2

步骤1 ：使用筛法生成一个包含2n以内的质数列表。

步骤2 ：寻找最接近的质数。

步骤3 ：使用筛法生成一个质数列表，通过消除每个质数的所有倍数直到其平方根。

步骤4 ：通过在质数列表中检查输入数上下的数来寻找最接近的质数。

步骤5 ：打印输入数最接近的质数。

语法

在Java中，Array.length方法返回给定数组的长度。

以下是其语法-

prime.lenght

‘prime’是一个数组。

多种方法

我们以不同的方法提供了解决方案。

通过使用蛮力方法
通过使用筛法

让我们逐个查看程序和输出。

方法一：通过使用蛮力方法

在这种方法中，程序将初始化一个整数。然后通过使用蛮力方法找到最接近的质数。

示例

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.

方法二：使用筛子法

在这种方法中，程序将初始化一个整数。然后使用筛子法生成一个素数列表，然后找到最接近的素数。

示例

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);
   }
}