Write a Java Program to Check Whether a Number can be Expressed as Sum of Two Prime Numbers

In this tutorial, we’ll explore how to write a Java program that checks whether a number can be expressed as the sum of two prime numbers.

Before we dive into the code, let’s quickly review what prime numbers are.

A prime number is a positive integer greater than 1 that has no positive integer divisors other than 1 and itself.

For example, 2, 3, 5, 7, 11, and 13 are all prime numbers.

Now, let’s get back to our problem at hand.

To check whether a number can be expressed as the sum of two prime numbers, we can iterate through all the possible pairs of prime numbers and see if any of them add up to the given number.

To generate a list of prime numbers, we can use the Sieve of Eratosthenes algorithm.

This algorithm works by creating a boolean array of all numbers up to a certain limit (the number we want to check in this case) and initially setting all the values to true.

We then iterate through the array, marking all multiples of each prime number as false, since they cannot be prime.

After we have finished iterating through the array, all remaining true values represent prime numbers.

Here’s the code to generate a list of prime numbers using the Sieve of Eratosthenes algorithm:

public static boolean[] sieveOfEratosthenes(int limit) {
    boolean[] isPrime = new boolean[limit + 1];
    Arrays.fill(isPrime, true);

    for (int i = 2; i * i <= limit; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= limit; j += i) {
                isPrime[j] = false;
            }
        }
    }

    return isPrime;
}

Now that we have a list of prime numbers, we can iterate through all the possible pairs of primes and see if any of them add up to our target number.

Here’s the code to do that:

public static boolean isSumOfTwoPrimes(int n) {
    boolean[] isPrime = sieveOfEratosthenes(n);

    for (int i = 2; i <= n / 2; i++) {
        if (isPrime[i] && isPrime[n - i]) {
            return true;
        }
    }

    return false;
}

In this code, we iterate through all values of i from 2 to n/2. For each value of i, we check if both i and n-i are prime.

If they are, we return true since n can be expressed as the sum of two prime numbers.

If we iterate through all possible values of i and do not find a pair of primes that add up to n, we return false.

That’s it!

We now have a Java program that can check whether a number can be expressed as the sum of two prime numbers.

Here’s the complete code:

import java.util.Arrays;

public class PrimeSum {
    public static boolean[] sieveOfEratosthenes(int limit) {
        boolean[] isPrime = new boolean[limit + 1];
        Arrays.fill(isPrime, true);

        for (int i = 2; i * i <= limit; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= limit; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        return isPrime;
    }

    public static boolean isSumOfTwoPrimes(int n) {
        boolean[] isPrime = sieveOfEratosthen
          for (int i = 2; i <= n / 2; i++) {
        if (isPrime[i] && isPrime[n - i]) {
            return true;
        }
    }

    return false;
}

public static void main(String[] args) {
    int n = 34;
    if (isSumOfTwoPrimes(n)) {
        System.out.println(n + " can be expressed as the sum of two prime numbers.");
    } else {
        System.out.println(n + " cannot be expressed as the sum of two prime numbers.");
    }
}

In the `main` method, we test our `isSumOfTwoPrimes` method by passing in the number 34.

We then print out a message indicating whether 34 can be expressed as the sum of two prime numbers.

That’s it for this tutorial!

We’ve learned how to check whether a number can be expressed as sum of two prime numbers.

Tags

Related Posts