# Goldbach's Conjecture using Sieve of Eratosthenes

I created a simple Java program to calculate Goldbach's conjecture and I was wondering how I could improve it (besides using clearer prompt messages).

/* Title: Goldbach Conjecture
* Author: Harris R
*/

import java.util.Scanner;

public class Goldbach
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Please input an integer to find two prime numbers whose sum add up to it.");
int input = scan.nextInt();
if(input < 4)
{
System.out.println("Number must be greater than or equal to 4");
return;
}
if(input%2 > 0)
{
System.out.println("Number must be even.");
return;
}
long startTime = System.nanoTime();
int[] primes = generatePrimes(input);
findPairs(input, primes);
long endTime = System.nanoTime();
System.out.println("\n This program took: " + (endTime-startTime) + " nanoseconds or " + ((endTime-startTime)*1e-9) + " seconds.");
}

private static int[] generatePrimes(int max)
{
boolean[] isComposite = new boolean[max + 1];
for (int i = 2; i * i <= max; i++)
{
if (!isComposite [i])
{
for (int j = i; i * j <= max; j++)
{
isComposite [i*j] = true;
}
}
}
int numPrimes = 0;
for (int i = 2; i <= max; i++)
{
if (!isComposite [i]) numPrimes++;
}
int [] primes = new int [numPrimes];
int index = 0;
for (int i = 2; i <= max; i++)
{
if (!isComposite [i]) primes [index++] = i;
}
return primes;
}

private static void findPairs(int input, int[] primes)
{
String primepairs = "";
for(int i = 0; i < primes.length; i++)
{
for(int j = i; j < primes.length; j++)
{
int p = primes[i];
int q = primes[j];
if(p+q == input)
{
primepairs += "\n" + q + " + " + p + " = " + input;
}
}
System.out.println("Program Completion: " + (((double)i/primes.length)*100) + "%");
}
System.out.println(primepairs);
}
}


## Efficiency

Post-processing the results from the Sieve of Eratosthenes (isComposite) to produce primes is actually counterproductive. If the findPairs() code just has a list of primes to work with, then it cannot quickly answer "is n a prime?" for any given n. Hence, you need to try all pairs of primes, making findPairs() O(|P|2), where |P| is the size of the set of primes. And that's in addition to the work needed to find those primes.

You would be better off using the raw isComposite array. Then, for any given p, you can immediately find out whether input - p is also prime.

## Code organization

Mixing input/output code with computation code is poor practice. I suggest using an Iterator<Integer> to iterate through the results. Then you can use a nice simple loop in main() to print the results.

Instead of System.out.println(… + … + … + …), use System.out.printf(), which is more readable. (Actually, System.err would be a better place to send diagnostic output.)

## Suggested solution

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Scanner;

public class GoldbachSums implements Iterable<Integer> {
private final int sum;
private final boolean[] ineligible;

public GoldbachSums(int sum) {
if (sum <= 2) {
throw new IllegalArgumentException("Number must be greater than 2.");
}
if (sum % 2 > 0) {
throw new IllegalArgumentException("Number must be even.");
}
this.sum = sum;
this.ineligible = oddSieveOfEratosthenes(sum);
}

private static boolean[] oddSieveOfEratosthenes(int max) {
boolean[] ineligible = new boolean[max];
ineligible[1] = true;
for (int i = 3; i * i < max; i += 2) {
if (! ineligible[i]) {
for (int j = i * i; j < max; j += i) {
ineligible[j] = true;
}
}
}
return ineligible;
}

@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
// 4 is the only sum whose decomposition involves an even prime
private Integer n = (sum == 4) ? 2 : computeNext(sum - 1);
private final int halfSum = sum / 2;

private Integer computeNext(int n) {
for (int i = n; i >= halfSum; i -= 2) {
if (!ineligible[i] && !ineligible[sum - i]) {
return sum - i;
}
}
return null;
}

@Override
public boolean hasNext() {
return n != null;
}

@Override
public Integer next() {
if (n == null) {
throw new NoSuchElementException();
} else try {
return n;
} finally {
n = computeNext(sum - n - 2);
}
}

// For compatibility with Java < 8
public void remove() {
throw new UnsupportedOperationException();
}
};
}

public static void main(String[] args) {
try (Scanner scan = new Scanner(System.in)) {
System.out.print("Please input an integer to decompose as the sum of two primes: ");
int input = scan.nextInt();

long startTime = System.nanoTime();
GoldbachSums goldbach = new GoldbachSums(input);
long duration = System.nanoTime() - startTime;
System.err.printf("\nSieve of Eratosthenes took: %d ns or %f seconds.\n",
duration, duration * 1e-9);
duration = System.nanoTime() - startTime;
for (int addend : goldbach) {
};
System.err.printf("\nThis program took: %d ns or %f seconds.\n",
duration, duration * 1e-9);
}
}
}


I'd change findPairs() to be a bit smarter about the way it searches. Instead of having nested for loops and starting the i and j pointers together, start the two pointers at opposite ends of the array, and converge them until they meet (at which point you're done). This way you reduce the time complexity of the algorithm by taking advantage of the fact that primes is ordered. Here's an example:

http://introcs.cs.princeton.edu/java/14array/Goldbach.java.html