Balanced Prime Number in Java

This section will cover the definition of a balanced prime number as well as how to find one using a Java program.

Balance Prime Number

A prime number that is equivalent to the average of the immediately preceding and following prime numbers is said to be balanced.

Let's use examples to better grasp it.

Example 1:

Input: 13

The result is that 13 is an unbalanced prime number.

Reason: The prime number that comes after the number 13 is 17, and the prime number that comes before it is 11. Their average is (11 + 17) / 2 = 28 / 2 = 14, which is not the same as the number 13. 13 is not an balanced prime number as a result.

Example 2:

Input: 53

53 is a prime number that is balanced.

Explanation: The prime number that is right after the value 53 is 59, and the prime number that is right before the number 53 is 47. The average of these two prime numbers is (47 + 59) / 2 = 106 / 2 = 53, that is the same as the input number. 53 is indeed a balanced prime number as a result.

Naive Approach

In this method, we'll employ two distinct loops. One is used to calculate the prime number that comes right after the input prime number, and the other is used to calculate the prime number that comes right after it. Then, in order to determine if the average is equal to an input prime number or not, we calculate the average of immediately preceding and following prime numbers. Take note of the program below.

BalancedPrimeExpl1.java

public class BalancedPrimeExpl1   
{  
public boolean isPrime(int n)  
{  
if(n == 0 || n == 1)  
{  
return false;  
}  
// Since the Math.sqrt method
// returns double, we must 
// modify it to int.  
int m = (int)Math.sqrt(n);  
for(int j = 2; j <= m; j++)  
{  
if(n % j == 0)  
{  
// reaching here indicates 
// that we have a factor that 
// is not 1, and therefore num 
// is not prime, so we return false. 
return false;  
}  
}  
return true;  
}  
public boolean isBalancedPrime(int n)  
{  
float g = n;  
// to store the previous prime we 
// keep the current n as the reference  
float pN = -1f;  
// for storing the next prime by  
// keeping the current num as the reference  
float nextNum = -1f;  
// finding the immediate previous prime  
for(float j = n - 1f; j >= 2f; j--)  
{  
if(isPrime((int)j))  
{  
// immediate previous prime has been found  
// so we can break the loop  
pN = j;  
break;  
}  
}  
// finding the immediate next prime  
for(float k = n + 1f; true; k++)  
{  
if(isPrime((int)k))  
{  
// immediate next prime has been found  
// so we can break the loop  
nextNum = k;  
break;  
}  
}  
if(pN == -1f)  
{       
// the previous prime number   
// is not found so we have
// reached here 
return false;  
}  
// calculating the average of the p and the nextNum  
float a = (pN + nextNum) / 2f;  
if(g == a)  
{  
return true;  
}  
return false;  
}  
public static void main(String args[])  
{  
// creating an instance for the class BalancedPrimeExpl1  
BalancedPrimeExpl1 o = new BalancedPrimeExpl1();  
  
System.out.println(" Total number of balanced primes are: ");  
  
for(int j = 1; j <= 200; j++)  
{  
if(o.isPrime(j) && o.isBalancedPrime(j))  
{  
System.out.print(j + " ");  
}  
}  
}  
}  

Output:

Time complexity:

A prime number num is taken into consideration along with the assumptions that the immediately preceding prime number is m distances away from num and the immediately following prime number is n distances away from num. Assume that k is the biggest number you've found while looking for the immediately preceding prime number, and l is the biggest number you've found while looking for the immediately following prime number. As a result, the program has an O(m + n) time complexity for each num.

It is annoying because, in order to calculate the immediately following and immediately preceding prime numbers, we must examine each number's previous value as well as its next value. We can utilize the filter invented by Eratosthenes to prevent that. Keep in mind the following.

Using the Sieve of Eratosthenes Algorithm

BalancedPrimeExpl2.java

public class BalancedPrimeExpl2  
{  
public boolean primeArr[];  
public void sieveofNumbers(int m)  
{  
// making a boolean primeArr[0... n] array and setting each
//  entry's initial value to true. 
// If k is not a prime number, the value of 
// primeArr[j] will ultimately be false, otherwise true.
primeArr = new boolean[m + 1];  
for(int j = 0; j <= m; j++)  
{  
primeArr[j] = true;  
}  
for(int k = 2; k * k <= m; k++)  
{  
// If primeArr[k] is not changing, then it is a prime number  
if(primeArr[k] == true)  
{  
// updating all the multiples of k 
for(int j = k * k; j <= m; j += k)  
{  
primeArr[j] = false;  
}  
}  
}  
}  
public boolean isBalancedPrime(int n)  
{  
float g = n;  
// to store the previous prime we  
// keep the current num as the reference  
float pN = -1f;  
// to store the next prime we  
// keep the current num as the reference  
float nextNum = -1f;  
// finding the immediate previous prime  
for(float j = n - 1f; j >= 2f; j--)  
{  
if(primeArr[(int)j])  
{  
// after the previous prime is found  
// we can break the loop  
pN = j;  
break;  
}  
}  
// finding the immediate next prime  
for(float k = n + 1f; true; k++)  
{  
if(primeArr[(int)k])  
{  
// after the next prime is found  
// we can break the loop  
nextNum = k;  
break;  
}  
}  
if(pN == -1f)  
{      
// the previous prime number   
// is not found so we
//  are reaching here 
return false;  
}  
// calculating the average of the pN and the nextNum  
float a = (pN + nextNum) / 2f;  
if(g == a)  
{  
return true;  
}  
return false;  
}  
public static void main(String args[])  
{  
// creating an instance for the class BalancedPrimeExpl2  
BalancedPrimeExpl2 o = new BalancedPrimeExpl2();  
o.sieveofNumbers(300);  
System.out.println(" Total number of balanced primes are : ");  
for(int j = 1; j <= 200; j++)  
{  
if(o.primeArr[j] && o.isBalancedPrime(j))  
{  
System.out.print(j + " ");  
}  
}  
}  
}

Output:

Time complexity:

The temporal complexity of the aforementioned program is O(m + n + k.log(k)) for any prime number num, where m is the distance between the prime number and num that comes immediately before it and n is the distance between num and the prime number that comes immediately after it. For which the sieve is calculated, k is the range.

Remember

If the sum of the immediately following prime number and the immediately smaller prime number is less than a prime number num, that number is said to be a weak prime number.

A prime number is said to be a strong prime number if the average of the two prime numbers right after it and the one right before it is greater than the number num.