Goldbach Number Pairs in Java: Algorithm, Program, Dry Run, Examples and Viva Questions

A Goldbach Number is an even natural number greater than 4 that can be expressed as the sum of two odd prime numbers. Finding all possible pairs of prime numbers whose sum equals a given even number is an interesting programming problem that combines prime number checking, loops, conditional statements and mathematical operations.

In Java, this problem can be solved by checking successive odd numbers, determining whether they are prime and finding their corresponding complements.

Let us understand the concept, develop the algorithm, write the Java program and examine its working through examples and a detailed dry run.

What Is a Goldbach Number?

An even natural number greater than 4 is called a Goldbach Number if it can be expressed as the sum of two odd prime numbers.

For example, consider the number 10.

It can be expressed as:

• 3 + 7 = 10
• 5 + 5 = 10

Both pairs consist of odd prime numbers. Therefore, 10 is a Goldbach Number.

Consider another example, 28.

Its possible prime pairs are:

• 5 + 23 = 28
• 11 + 17 = 28

Notice that each pair is displayed only once, with the smaller prime number appearing first.

Important: The Goldbach conjecture states that every even integer greater than 2 can be expressed as the sum of two primes. The program discussed here checks even numbers in the specified range of 6 to 50.

Algorithm to Find Goldbach Number Pairs

The program follows a systematic approach to identify all possible pairs of odd prime numbers whose sum equals the given even number.

Step-by-step algorithm:

1. Start.
2. Accept an even integer N from the user.
3. Check whether N lies between 6 and 50 and is even.
4. If the input is invalid, display an appropriate error message.
5. Initialise a variable count to 0.
6. Run a loop with i starting from 3 and continuing up to N / 2, incrementing it by 2.
7. Calculate the complementary number using j = N – i.
8. Check whether both i and j are prime using the isPrime() method.
9. If both numbers are prime:
   • Display the pair i + j = N.
   • Increment count.
10. After completing the loop, check the value of count.
11. If count is 0, display that no prime pairs were found.
12. Stop.

Java Program to Find Goldbach Number Pairs

The following program uses separate user-defined methods for prime number checking and displaying Goldbach pairs. This approach improves code readability and makes the program easier to understand.

import java.util.Scanner;
class Goldbach
{
// Method to check whether a number is prime
boolean isPrime(int n)
{
if(n < 2)
return false;

    for(int i = 2; i <= Math.sqrt(n); i++)
    {
        if(n % i == 0)
            return false;
    }

    return true;
}
// Method to display Goldbach pairs
void display(int n)
{
    int count = 0;

    System.out.println("Goldbach pairs for " + n + ":");

    for(int i = 3; i <= n / 2; i += 2)
    {
        int j = n - i;

        if(isPrime(i) && isPrime(j))
        {
            System.out.println(i + " + " + j + " = " + n);
            count++;
        }
    }
    if(count == 0)
        System.out.println("No prime pairs found.");
}
public static void main(String args[])
{
    Scanner sc = new Scanner(System.in);
    Goldbach ob = new Goldbach();
    System.out.print("Enter an even number (6 to 50): ");
    int n = sc.nextInt();
    if(n >= 6 && n <= 50 && n % 2 == 0)
    {
        ob.display(n);
    }
    else
    {
        System.out.println("Invalid Input!");
        System.out.println("Enter an even number between 6 and 50.");
    }
}

}

Explanation of the Methods

isPrime(int n)

This method checks whether the supplied number is prime.

• If the number is less than 2, it returns false.
• It checks divisibility from 2 up to the square root of the number.
• If any divisor is found, it returns false.
• Otherwise, it returns true.

display(int n)

This method identifies and displays all possible Goldbach pairs.

• It starts with an odd number, 3.
• It calculates the complementary number using j = n – i.
• It checks whether both numbers are prime.
• If both are prime, the pair is displayed.
• A counter variable records the total number of valid pairs.

main()

The main method accepts an integer from the user and validates whether it is even and within the specified range of 6 to 50. If valid, it invokes the display() method.

Understanding the Important Loop

Consider the following statement:

for(int i = 3; i <= n / 2; i += 2)

This is one of the most important parts of the program.

Let us understand its three components:

• int i = 3: The loop begins with 3 because the problem requires odd prime numbers.
• i <= n / 2: The loop continues only up to half of the given number.
• i += 2: The loop increments by 2, ensuring that only odd numbers are checked.

Why do we use N / 2?

Suppose the given number is 20.

We know that:

20 = 3 + 17

If we continue checking numbers beyond 10, we will simply obtain the same pairs in reverse order.

For example:

• 3 + 17 = 20
• 17 + 3 = 20

These are not two different pairs. They represent the same combination.

Therefore, checking only up to N / 2 prevents duplicate pairs and ensures that the smaller prime number always appears first.

Remember: The condition i <= n / 2 is used to avoid displaying duplicate combinations.

Sample Executions

Execution 1: Input = 10

Enter an even number (6 to 50): 10

Goldbach pairs for 10:

3 + 7 = 10

5 + 5 = 10

Explanation: The number 10 can be expressed as the sum of two odd prime numbers in two different ways. Therefore, two Goldbach pairs are displayed.

Execution 2: Input = 28

Enter an even number (6 to 50): 28

Goldbach pairs for 28:

5 + 23 = 28

11 + 17 = 28

Explanation: The program checks all possible odd prime candidates up to 14.

Although 3 + 25 = 28 is mathematically a possible sum, 25 is not prime. Therefore, this pair is rejected.

The valid pairs are 5 + 23 and 11 + 17.

Execution 3: Input = 9

Enter an even number (6 to 50): 9

Invalid Input!

Enter an even number between 6 and 50.

Explanation: The number 9 is odd. Since the problem requires an even integer, the program displays an invalid input message.

Execution 4: Input = 6

Enter an even number (6 to 50): 6

Goldbach pairs for 6:

3 + 3 = 6

Explanation: The smallest valid input is 6, which can be expressed as the sum of two odd prime numbers, 3 and 3.

Dry Run for N = 20

Let us understand the execution of the program by tracing each iteration of the loop.

Given:

N = 20

The loop executes with i taking the values 3, 5, 7 and 9 because the condition is i <= N / 2.

The complementary number is calculated using:

int j = n – i;

Dry Run Table

Explanation of Each Iteration

Iteration 1:

• i = 3
• j = 20 – 3 = 17
• Both 3 and 17 are prime.
• Therefore, the pair 3 + 17 is displayed.

Iteration 2:

• i = 5
• j = 20 – 5 = 15
• 5 is prime, but 15 is not prime.
• Therefore, the pair is rejected.

Iteration 3:

• i = 7
• j = 20 – 7 = 13
• Both 7 and 13 are prime.
• Therefore, the pair 7 + 13 is displayed.

Iteration 4:

• i = 9
• j = 20 – 9 = 11
• 9 is not prime, although 11 is prime.
• Therefore, the pair is rejected.

Final Output

Goldbach pairs for 20:

3 + 17 = 20

7 + 13 = 20

Important Concepts Used in the Program

Why is && used?

Consider:

if(isPrime(i) && isPrime(j))

The logical AND operator (&&) ensures that both conditions must be true.

• If i is prime and j is prime, the pair is accepted.
• If either number is not prime, the pair is rejected.

For example, in the case of 20:

isPrime(5) && isPrime(15)

The first condition returns true, but the second returns false. Therefore, the entire expression evaluates to false.

Important Examination Tips

Students should remember the following points while writing this program in their practical examination:

1. Always validate the input before processing it.
2. Start the loop from 3 because only odd prime numbers are required.
3. Use i += 2 to skip even numbers.
4. Calculate the complementary number using j = n – i.
5. Check both numbers independently for primality.
6. Use the logical AND operator (&&) to ensure that both numbers are prime.
7. Run the loop only up to n / 2 to avoid duplicate pairs.
8. Initialise the counter to zero before entering the loop.
9. Display the pairs in ascending order, with the smaller prime number first.

Conclusion

The Goldbach Number Pairs program is an excellent practical examination problem that tests a student’s understanding of prime number checking, loops, conditional statements, logical operators and user-defined methods.

The most important part of the solution is the use of N / 2 as the loop limit. It eliminates duplicate pairs and ensures that every valid combination is displayed only once.

By understanding the algorithm and tracing the dry run, students can confidently solve similar programming problems involving prime numbers and mathematical combinations in Java.

Important Viva Questions and Answers

Q1. What is a Goldbach Number?

An even natural number greater than 4 that can be expressed as the sum of two odd prime numbers is called a Goldbach Number.

Q2. What is the Goldbach conjecture?

It is a mathematical conjecture stating that every even integer greater than 2 can be expressed as the sum of two prime numbers.

Q3. Why does the loop start from 3?

Because the problem requires odd prime numbers, and 3 is the smallest odd prime number.

Q4. Why is i += 2 used instead of i++?

It skips all even numbers and checks only odd numbers, reducing unnecessary iterations.

Q5. Why does the loop run only up to n / 2?

To prevent duplicate pairs and ensure that the smaller prime number appears first.

Q6. What is the purpose of j = n – i?

It calculates the complementary number required to make the sum equal to the given number.

Q7. Why is a counter variable used?

The variable count records the total number of valid Goldbach pairs. It also helps determine whether any valid pair was found.

Q8. Can both prime numbers in a pair be equal?

Yes. For example, 6 = 3 + 3 and 10 = 5 + 5.

Q9. Is 28 a Goldbach Number?

Yes. Its valid prime pairs are 5 + 23 and 11 + 17.

Q10. Why is Math.sqrt(n) used in the prime-checking method?

A number only needs to be checked for divisibility up to its square root because any factor greater than the square root must have a corresponding factor smaller than it.

Q11. What happens if the input number is odd?

The validation condition fails, and the program displays an invalid input message.

Q12. What is the purpose of count == 0?

It checks whether the program found any valid Goldbach pairs. If the counter remains zero, the program displays an appropriate message.