Java 程序寻找最接近的素数
javaobject oriented programmingprogramming更新于 2024/8/4 21:23:00
素数是大于 1 的正整数，只能被 1 和自身整除。
素数是数学和计算机科学中的一个重要概念。它们是只能被 1 和自身整除的整数。寻找素数是许多算法中的重要任务，有几种方法可以确定一个数字是否为素数。其中一个问题就是找到最接近给定数字的素数。
在这里，我们将探索如何找到任何数字的最接近的素数。
让我们开始吧!
例如
给定整数:15
最接近的素数:13
算法
算法 1
步骤 1:检查输入数字是否为素数。
步骤 2:如果输入数字为素数，程序将打印该数字并退出。
步骤 3:如果输入数字不是素数，程序将通过检查输入数字前后的数字来查找最接近的素数。
步骤 4:使用使用蛮力法检查某个数字是否为素数，方法是检查所有数字直到其平方根。
步骤 5:打印最接近输入数字的素数。
算法 2
步骤 1:使用筛选法生成一个最多 2n 个素数的列表。
步骤 2:检查最接近输入数字的素数。
步骤 3:使用筛选法生成一个素数列表，方法是消除每个素数的所有倍数直到其平方根。
步骤 4:通过检查素数列表中输入数字上方和下方的数字来检查最接近的素数。
步骤 5:打印最接近输入的素数数字。
语法
Java 中的 Array.length 方法返回给定数组的长度。
下面引用它的语法-
prime.lenght
其中，"prime"是指数组。
多种方法
我们提供了不同方法的解决方案。
通过使用蛮力方法
通过使用筛选方法
让我们逐一查看程序及其输出。
方法 1:通过使用蛮力方法
在这种方法中，将在程序。然后使用蛮力方法找到最接近的素数。
示例
public class Main {
// 检查数字是否为素数的函数
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;
}
// 通过检查输入数字上方和下方的数字来找到最接近的素数
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.
方法 2:使用筛选法
在此方法中，程序中将初始化一个整数。然后使用筛选法生成一个素数列表，然后找到最接近的素数。
示例
import java.util.Arrays;
public class Main {
// 函数用于生成达到给定限制的素数列表
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;
}
// 查找与给定数字最接近的素数的函数
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;
// 生成最多 2n 个素数的列表
boolean[] prime = sieve(2*n);
// 找到最接近 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 编程语言检查最接近素数的不同方法。
