Java Program for Closest Prime Number

A prime number is a positive integer greater than 1 that is only divisible by 1 and itself. Prime numbers are an essential concept in mathematics and computer science. They are integers that are only divisible by 1 and themselves.

Finding prime numbers is an important task in many algorithms, and there are several methods to determine if a number is prime. One such problem is finding the closest prime number to a given number.

Problem Statement

For a given number find the closest prime number by using Java programming language. Consider the following example -

Input

54

Output

53 is the closest prime number to 54.

Different Approaches to Find Closest Prime Number

We have provided the solution in different approaches.

• Using Brute-Force Approach
• Using Sieve Approach

Find the Closest Prime Number Using Brute-Force Approach

In this approach, an integer will be initialized in the program. Then by using brute-force approach finding the closest possible prime number.

Algorithm for Brute-Force Approach

• Step 1: Check if the input number is prime or not.
• Step 2: If the input number is prime, the program prints the number and exits.
• Step 3: If the input number is not prime, the program checks for the closest prime number by checking numbers before and after the input number.
• Step 4: Use a Brute-force approach to check if a number is prime by checking all numbers up to its square root.
• Step 5: Print the closest prime number to the input number.

Example

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

Output

53 is the closest prime number to 54.

Find the Closest Prime Number Using Sieve Approach

In this approach, an integer will be initialized in the program. Then by using sieve approach generate a list of prime number and then finding the closest possible prime number.

Algorithm for Sieve Approch

• Step 1: Generate a list of prime numbers up to 2n using a Sieve approach.
• Step 2: Check for the closest prime number to the input number.
• Step 3: Use a Sieve approach to generate a list of prime numbers by eliminating all multiples of each prime number up to its square root.
• Step 4: Check for the closest prime number by checking numbers above and below the input number in the list of prime numbers.
• Step 5: Print the closest prime number to the input number.

Example

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

Output

The closest prime number to 27 is 29

In this article, we explored different approaches to check closest prime number by using Java programming language.