Java 中的平衡素数

2024年9月10日 | 阅读 6 分钟

在本节中，我们将讨论什么是平衡素数以及如何通过 Java 程序找到平衡素数。

平衡素数

平衡素数是指一个素数，它等于其紧邻的下一个素数和紧邻的上一个素数的平均值。

让我们通过示例来理解。

示例 1

输入 13

输出：13 不是平衡素数。

解释：紧邻数字 13 的素数是 17，紧邻数字 13 的上一个素数是 11，它们的平均值是 (11 + 17) / 2 = 28 / 2 = 14，不等于 13。因此，13 不是平衡素数。

示例 2

输入 53.

输出：53 是平衡素数。

解释：紧邻数字 53 的素数是 59，紧邻数字 53 的上一个素数是 47，它们的平均值是 (47 + 59) / 2 = 106 / 2 = 53，等于输入数字。因此，53 是平衡素数。

朴素方法

在这种方法中，我们将使用两个独立的循环。一个用于计算紧邻的上一个素数，另一个用于计算紧邻的下一个素数，以输入素数为参考。然后，我们计算紧邻的上一个和紧邻的下一个素数的平均值，并将其与输入数字进行比较，以检查平均值是否等于输入素数。请看以下程序。

文件名：BalancedPrime.java

public class BalancedPrime 
{
// a method that checks whether the number num 
// is a prime number or not
public boolean isPrime(int num)
{
if(num == 0 || num == 1)
{
return false;
}
// Math.sqrt method returns double
// therefore, we have to change it to int
int n = (int)Math.sqrt(num);
for(int i = 2; i <= n; i++)
{
if(num % i == 0)
{
// reaching here means we have got 
// a factor that is not 1 and the number num
// hence the number num is not prime, and we 
// return false
return false;
}
}
return true;
}
public boolean isBalancedPrime(int num)
{
float f = num;
// for storing the previous prime by
// keeping the current num as the reference
float prvNum = -1f;
// for storing the next prime by
// keeping the current num as the reference
float nextNum = -1f;
// computing the immediate previous prime
for(float i = num - 1f; i >= 2f; i--)
{
if(isPrime((int)i))
{
// immediate previous prime is found
// we can terminate the loop
prvNum = i;
break;
}
}
// computing the immediate next prime
for(float j = num + 1f; true; j++)
{
if(isPrime((int)j))
{
// immediate next prime is found
// we can terminate the loop
nextNum = j;
break;
}
}
if(prvNum == -1f)
{   
// reaching here means
// the previous prime number 
// is not found
return false;
}
// computing the average of the prvNum and the nextNum
float avg = (prvNum + nextNum) / 2f;
if(f == avg)
{
return true;
}
return false;
}
public static void main(String argvs[])
{
// creating an object of the class BalancedPrime
BalancedPrime obj = new BalancedPrime();

System.out.println("Total number of balanced primes from 1 to 200 is: ");

for(int i = 1; i <= 200; i++)
{
// balance prime is also a prime number
if(obj.isPrime(i) && obj.isBalancedPrime(i))
{
System.out.print(i + " ");
}
}
}
}

输出

Total number of balanced primes from 1 to 200 is: 
5 53 157 173

时间复杂度：如果我们考虑一个素数 *num*，我们也假设紧邻的上一个素数距离 *num* 为 *m*，紧邻的下一个素数距离 *num* 为 *n*。还假设在搜索紧邻的上一个素数时遇到的最大数字是 k，在搜索紧邻的下一个素数时遇到的最大数字是 l。因此，对于每个 num，程序的时间复杂度为 **O(m + n )**。

为每个数字计算紧邻的下一个素数和上一个素数，需要检查每一个之前的数字和之后的数字，这很麻烦。为了避免这种情况，我们可以使用埃拉托斯特尼筛法。请看以下内容。

使用埃拉托斯特尼筛法

文件名：BalancedPrime1.java

public class BalancedPrime1
{
public boolean primeArr[];
// a method that uses the sieve of Eratosthenes
// to filter out the prime numbers
public void sieveofNumbers(int n)
{
// Creating an array of type boolean primeArr[0 ... n]" and initializing
// all the entries with the true value. The value of primeArr[j] will be
// finally the false value if j is not the prime, otherwise true.
primeArr = new boolean[n + 1];
for(int i = 0; i <= n; i++)
{
primeArr[i] = true;
}
for(int j = 2; j * j <= n; j++)
{
// If primeArr[j] is not getting changed, then it is a prime
if(primeArr[j] == true)
{
// Updating all of the multiples of j
for(int i = j * j; i <= n; i += j)
{
primeArr[i] = false;
}
}
}
}
public boolean isBalancedPrime(int num)
{
float f = num;
// for storing the previous prime by
// keeping the current num as the reference
float prvNum = -1f;
// for storing the next prime by
// keeping the current num as the reference
float nextNum = -1f;
// computing the immediate previous prime
for(float i = num - 1f; i >= 2f; i--)
{
if(primeArr[(int)i])
{
// immediate previous prime is found
// we can terminate the loop
prvNum = i;
break;
}
}
// computing the immediate next prime
for(float j = num + 1f; true; j++)
{
if(primeArr[(int)j])
{
// immediate next prime is found
// we can terminate the loop
nextNum = j;
break;
}
}
if(prvNum == -1f)
{   
// reaching here means
// the previous prime number 
// is not found
return false;
}
// computing the average of the prvNum and the nextNum
float avg = (prvNum + nextNum) / 2f;
if(f == avg)
{
return true;
}
return false;
}
public static void main(String argvs[])
{
// creating an object of the class BalancedPrime1
BalancedPrime1 obj = new BalancedPrime1();
obj.sieveofNumbers(300);
System.out.println("Total number of balanced primes from 1 to 200 is: ");
for(int i = 1; i <= 200; i++)
{
// balance prime is also a prime number
if(obj.primeArr[i] && obj.isBalancedPrime(i))
{
System.out.print(i + " ");
}
}
}
}

输出

Total number of balanced primes from 1 to 200 is: 
5 53 157 173

时间复杂度：对于任何素数 *num*，上述程序的复杂度为 O(m + n + k.log(k))，其中 *m* 是紧邻的上一个素数与 *num* 之间的差距，*n* 是 *num* 与紧邻的下一个素数之间的差距。*k* 是计算筛法的范围。

注意事项

对于素数 *num*，如果紧邻的下一个素数和紧邻的更小素数的平均值小于数字 *num*，则 *num* 被称为弱素数。
对于素数 *num*，如果紧邻的下一个素数和紧邻的更小素数的平均值大于数字 *num*，则 *num* 被称为强素数。

下一主题Minecraft 基岩版与 Java 版的区别

Java 中的平衡素数

平衡素数

朴素方法

使用埃拉托斯特尼筛法

注意事项

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的平衡素数

平衡素数

朴素方法

使用埃拉托斯特尼筛法

注意事项

相关帖子

Java 中排序 Set

Java 中的按日期分组代码

Multiply Two Polynomials in Java

Java 泛型队列

Java 中的直线数

Java 泛型设计模式

如何打开 Java 控制面板

Java 中的驼峰命名法

Java 中的 Integer.valueOf() 方法

CollationElementIterator setOffset() method in Java with Examples

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器