ISC Practicals and Theory - Goldbach's Conjecture

Goldbach's Conjecture says that every even number greater than $2$ can be written as the sum of two prime numbers. This program, written in the main method alone, takes one even number, displays every way of writing it as a sum of two primes, and gives an error message for any other input.

Definition

Goldbach's Conjecture: every even number $N$ greater than $2$ is the sum of two prime numbers.

A prime number has exactly two factors: $1$ and the number itself.

• $10 = 3 + 7 = 5 + 5$
• $28 = 5 + 23 = 11 + 17$
• $4 = 2 + 2$

A pair such as $3 + 7$ and $7 + 3$ is the same way of writing the number, so the program shows each pair once, with the smaller prime first. The number is valid only if it is even and greater than $2$; an odd number, $2$, or a number below $2$ is invalid input.

Algorithm

1. Accept the number n. If n <= 2 or n is odd (n % 2 != 0), display Invalid input and stop.
2. Display the heading line and set ways = 0.
3. For a from 2 to n / 2, find the other number of the pair, b = n - a.
4. Count the factors of a in ca: for i from 1 to a, add 1 to ca whenever a % i == 0. If ca is 2, a is prime, so count the factors of b in cb in the same way.
5. If ca == 2 and cb == 2, both numbers are prime: display n = a + b and add 1 to ways.
6. After the loop, display the number of ways.

Program

The outer for loop in main tries each pair a and b, and the inner for loops count the factors to test for a prime. Only the pairs with a up to n / 2 are tried, so no pair is shown twice.

import java.util.Scanner;
public class Goldbach
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter an even number greater than 2: ");
        int n = sc.nextInt();                   // the even number
        if (n <= 2 || n % 2 != 0)
        {
            System.out.println("Invalid input");
        }
        else
        {
            System.out.println("The number " + n + " can be written as the sum of two primes in these ways:");
            int ways = 0;                       // number of pairs found
            for (int a = 2; a <= n / 2; a++)
            {
                int b = n - a;                  // the other number of the pair
                int ca = 0, cb = 0;             // number of factors of a and of b
                for (int i = 1; i <= a; i++)
                {
                    if (a % i == 0)
                        ca++;
                }
                if (ca == 2)                    // test b only when a is prime
                {
                    for (int i = 1; i <= b; i++)
                    {
                        if (b % i == 0)
                            cb++;
                    }
                }
                if (ca == 2 && cb == 2)         // both are prime
                {
                    System.out.println(n + " = " + a + " + " + b);
                    ways++;
                }
            }
            System.out.println("Number of ways = " + ways);
        }
    }
}

Variable description table

Sample input and output

Enter an even number greater than 2: 28
The number 28 can be written as the sum of two primes in these ways:
28 = 5 + 23
28 = 11 + 17
Number of ways = 2

Enter an even number greater than 2: 10
The number 10 can be written as the sum of two primes in these ways:
10 = 3 + 7
10 = 5 + 5
Number of ways = 2

Enter an even number greater than 2: 9
Invalid input

Enter an even number greater than 2: 2
Invalid input

Dry run

Input: n = 10. The outer loop runs for a from $2$ to $5$.

The loop ends after a = 5 (which is n / 2), and the program displays "Number of ways = 2", as in the second sample run.

Variations

1. Range: "Accept two positive integers m and n. Display every even number between m and n and the ways it can be written as the sum of two primes."
2. Recursive technique: "Write the prime test using a recursive method and use it to display the ways an even number is the sum of two primes."
3. Twin primes: "Display all twin prime pairs in a given range."
4. Prime numbers: "Display all prime numbers between m and n."