# Goldbach.java

Below is the syntax highlighted version of Goldbach.java from §1.4 Arrays.

```/******************************************************************************
*  Compilation:  javac Goldbach.java
*  Execution:    java -Xmx900MB -Xms900MB Goldbach n
*
*  Computes all primes less than n and tries to express n as a sum
*  of two primes. Goldbach's conjecture says that this is always
*  possible if n is even and greater than 2. When n is odd, these
*  are called prime pairs.
*
*  Sample execution:
*
*     % java Goldbach 10003292
*     10003292 = 349 + 10002943
*
*     % java Goldbach 10000001
*     10000001 is not expressible as the sum of two primes
*
*     % java Goldbach 10000021
*     10000021 = 2 + 10000019
*
******************************************************************************/

public class Goldbach {
public static void main(String[] args) {
int n = Integer.parseInt(args);

boolean[] isPrime = new boolean[n];

for (int i = 2; i < n; i++)
isPrime[i] = true;

// determine primes < n using Sieve of Eratosthenes
for (int factor = 2; factor*factor < n; factor++) {
if (isPrime[factor]) {
for (int j = factor; factor*j < n; j++)
isPrime[factor*j] = false;
}
}

// count primes
int primes = 0;
for (int i = 2; i < n; i++)
if (isPrime[i]) primes++;

System.out.println("Done tabulating primes.");

// store primes in list
int[] list = new int[primes];
int count = 0;
for (int i = 0; i < n; i++)
if (isPrime[i]) list[count++] = i;

// check if n can be expressed as sum of two primes
int left = 0, right = count-1;
while (left <= right) {
if      (list[left] + list[right] == n) break;
else if (list[left] + list[right]  < n) left++;
else right--;
}
if (list[left] + list[right] == n)
System.out.println(n + " = " + list[left] + " + " + list[right]);
else
System.out.println(n + " not expressible as sum of two primes");
}

}
```