Java Program To Check Whether A Number Can Be Expressed As Sum Of Two Prime Numbers

In this article, you will learn how to write a Java program to determine if a given number can be expressed as the sum of two prime numbers. We will explore a systematic approach, complete with code examples and detailed explanations.

Problem Statement

The challenge is to take an integer as input and ascertain whether it can be represented as the sum of two prime numbers. For instance, if the input is 10, it can be expressed as 3 + 7 or 5 + 5, where 3, 5, 7 are all prime numbers. This problem is a common exercise in number theory and programming logic, requiring an understanding of prime numbers and iterative checking.

Example

Let's consider the number 34.

• Input: 34
• Output: 34 can be expressed as sum of two prime numbers: 3 + 31

Background & Knowledge Prerequisites

To effectively understand and implement the solution, a basic grasp of the following Java concepts is essential:

• Variables and Data Types: Understanding how to declare and use integer variables.
• Conditional Statements: if-else statements for decision-making.
• Loops: for and while loops for iteration.
• Methods/Functions: How to define and call methods for modularizing code.
• Prime Numbers: A natural number greater than 1 that has no positive divisors other than 1 and itself. Examples: 2, 3, 5, 7, 11.

No special imports or complex setup are required beyond the standard Java Development Kit (JDK).

Use Cases or Case Studies

While the problem of expressing a number as the sum of two primes is often a theoretical or academic exercise, its underlying logic has applications and relevance in several areas:

• Number Theory Research: This problem touches upon concepts like Goldbach's Conjecture, an unproven hypothesis stating that every even integer greater than 2 is the sum of two prime numbers. Programming solutions help explore such conjectures computationally.
• Educational Tools: For students learning about prime numbers, factorization, and basic algorithms, this serves as an excellent practical problem to reinforce these concepts.
• Algorithm Development: It provides a simple scenario to practice designing helper functions (like isPrime) and combining them with iterative algorithms.
• Interview Questions: Similar logic puzzles are frequently encountered in technical interviews to assess problem-solving skills and understanding of fundamental data structures and algorithms.
• Cryptography (Foundational Understanding): While not directly used for cryptographic systems, the understanding of prime numbers and their properties is foundational to many modern encryption techniques (e.g., RSA relies on the difficulty of factoring large numbers into their prime components).

Solution Approaches

For this problem, the most straightforward and common approach involves iterating through possible prime numbers and checking if their sum equals the target number. This method combines a primality test with an iterative search.

Approach 1: Iterative Check with a Primality Test Function

This approach involves creating a helper function to determine if a number is prime, and then using this function within a loop to find two primes that sum up to the target number.

One-line summary: Iterate from 2 up to half the target number, checking if both the current number and its complement (target - current) are prime.

// Check if a Number Can be Expressed as Sum of Two Prime Numbers
import java.util.Scanner;

// Main class containing the entry point of the program
public class Main {

    // Helper method to check if a number is prime
    public static boolean isPrime(int num) {
        // Step 1: Handle base cases
        if (num <= 1) {
            return false; // Numbers less than or equal to 1 are not prime
        }
        // Step 2: Check for divisibility from 2 up to sqrt(num)
        // We only need to check up to the square root of num
        // because if a number n has a divisor d > sqrt(n),
        // then it must also have a divisor n/d < sqrt(n).
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                return false; // If divisible, it's not prime
            }
        }
        // Step 3: If no divisors found, it's prime
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Step 1: Prompt user for input
        System.out.print("Enter a positive integer: ");
        int number = scanner.nextInt();

        // Step 2: Initialize flag to track if sum is found
        boolean found = false;

        // Step 3: Iterate from 2 up to half of the input number
        // We iterate up to number/2 because if one prime (i) is greater than number/2,
        // then the other prime (number - i) must be less than number/2.
        // Checking both cases is redundant.
        for (int i = 2; i <= number / 2; i++) {
            // Step 4: Check if 'i' is prime
            if (isPrime(i)) {
                // Step 5: Calculate the complement 'j'
                int j = number - i;
                // Step 6: Check if 'j' is prime
                if (isPrime(j)) {
                    // Step 7: If both 'i' and 'j' are prime, we found a pair
                    System.out.println(number + " can be expressed as sum of two prime numbers: " + i + " + " + j);
                    found = true; // Set flag to true
                    break; // Exit the loop as we found at least one pair
                }
            }
        }

        // Step 8: If no such pair was found after checking all possibilities
        if (!found) {
            System.out.println(number + " cannot be expressed as sum of two prime numbers.");
        }

        scanner.close(); // Close the scanner
    }
}

Run

Sample Output:

For input 10:

Enter a positive integer: 10
10 can be expressed as sum of two prime numbers: 3 + 7

For input 34:

Enter a positive integer: 34
34 can be expressed as sum of two prime numbers: 3 + 31

For input 23:

Enter a positive integer: 23
23 cannot be expressed as sum of two prime numbers.

For input 4:

Enter a positive integer: 4
4 can be expressed as sum of two prime numbers: 2 + 2

Stepwise Explanation:

1. isPrime(int num) Method:

• This helper method takes an integer num and returns true if num is prime, false otherwise.
• It first handles edge cases: numbers less than or equal to 1 are not prime.
• It then iterates from 2 up to the square root of num. If num is divisible by any number in this range, it's not prime.
• If the loop completes without finding any divisors, the number is prime.

1. main(String[] args) Method:

• Get Input: A Scanner object is used to read an integer from the user.
• Initialize found Flag: A boolean variable found is set to false initially. This flag will become true if we find a pair of prime numbers that sum up to the input.
• Iterate Through Possible Primes: A for loop iterates from i = 2 up to number / 2.
• We only need to iterate up to number / 2 because if i is a prime number, and i > number / 2, then number - i would be less than number / 2. We would have already checked this pair when the loop variable was number - i.
• Check i's Primality: Inside the loop, isPrime(i) is called to check if the current number i is prime.
• Calculate Complement j: If i is prime, its complement j is calculated as number - i.
• Check j's Primality: The isPrime(j) method is then called to check if j is also prime.
• Found Pair: If both i and j are prime, the program prints the result, sets found to true, and breaks out of the loop (as we only need to find one such pair).
• No Pair Found: After the loop finishes, if found is still false, it means no pair of prime numbers was found that sums up to the input number, and an appropriate message is printed.
• Close Scanner: The scanner object is closed to release system resources.

Conclusion

Determining if a number can be expressed as the sum of two prime numbers is a fundamental problem that combines basic number theory with iterative programming logic. By implementing a reusable isPrime function, the overall solution becomes modular, readable, and efficient for reasonable input sizes. This approach efficiently checks all potential pairs, ensuring correctness.

Summary

• Problem: Check if a given integer can be represented as the sum of two prime numbers.
• Core Idea: Utilize a helper function to determine primality and then iterate through possible prime addends up to half the target number.
• isPrime Function: Efficiently checks if a number is prime by testing divisibility up to its square root.
• Main Logic: Loops from 2 to number / 2. For each i, if both i and (number - i) are prime, a solution is found.
• Efficiency: The isPrime function's sqrt(n) complexity combined with the main loop's n/2 iterations provides a practical solution for common input ranges.