# Goldbach conjecture solution finder

The Goldbach conjecture says: any even number greater than two can be represented by the sum of two prime numbers.

G(n) = { (p1, p2) | p1 + p2 = n, p1 and p2 are prime numbers with p1 < p2 }

For example:

G(6) = {(3, 3)}

G(12) = {(5, 7)}

G(26) = {(3, 23),(7, 19),(13, 13)}

So I have to do an algorithm that determines which three numbers n1, n2 and n3 are between 1,000,000 and 2,000,000 for which the G (n1), G (n2) and G (n3) have the largest number of elements.

I do not know if I need to improve something in my code, or even optimize some part that is poorly written. It currently taking about 12 seconds.

public class Goldbach  {

private static int j;
private static int k;
private static int [] primes;
private static int [] just_primes;
private static int [] conjunct;

public static void main(String[] args)
{

primes = new int[2000000];
for ( int i=0; i<2000000; i++ ) {
primes[i] = i+1;
}

for ( int i=1; i<1000000; i++ ) {
if ( primes[i] != 0 ) {
j = primes[i];
k = j;
while ( k <= 2000000 ) {
k += j;
if ( k <= 2000000 ) {
primes[ k-1 ] = 0;
}
}
}
}

just_primes = new int [primes.length];
for ( int i = 0; i< primes.length-1 ; i++ ) {
just_primes[i] = 0;
}

k = 0;
for ( int i = 1; i< primes.length-1 ; i++ ) {
if ( primes[i] > 0 ) {
just_primes[k] = primes[i];
k++;
}
}

conjunct = new int[1000001];
for ( int i = 0; i<1000001 ; i++ ) {
conjunct[i] = 0;
}

int p;
for ( int i = 0; i< k ; i++ ) {
for ( int j = i; j< k ; j++ ) {
int w = just_primes[i]+just_primes[j];
if ( w >= 1000000 && w <= 2000000 ) {
p = w - 1000000;
conjunct[p]++;
}
}
}

int big1 = 0;
int big2 = 0;
int big3 = 0;
int n1 = 0;
int n2 = 0;
int n3 = 0;

for ( int i = 0; i<1000001 ; i++ ) {
if ( conjunct[i] >= big1 ) {
big3 = big2;
big2 = big1;
big1 = conjunct[i];
n3 = n2;
n2 = n1;
n1 = i;
} else {
if ( conjunct[i] >= big2 ) {
big3 = big2;
big2 = conjunct[i];
n3 = n2;
n2 = i;
} else {
if ( conjunct[i] >= big3 ) {
big3 = conjunct[i];
n3 = i;
}
}
}
}

System.out.println( "Largest conjunct 1: " + n1 + " " + 1000000+big1 + " pairs" );
System.out.println( "Largest conjunct 2: " + n2 + " " + 1000000+big2 + " pairs" );
System.out.println( "Largest conjunct 3: " + n3 + " " + 1000000+big3 + " pairs" );

}

}


Expected result:

Largest conjunct 1: 981980 100000027988 pairs
Largest conjunct 2: 951950 100000027802 pairs
Largest conjunct 3: 995630 100000027730 pairs

• How are 981980, 951950, and 995630 "between 1,000,000 and 2,000,000"? – גלעד ברקן Apr 26 at 14:59
• Good point, he needs to add 10^6 to the number first. – Jorge Fernández Apr 26 at 15:01

## 1 Answer

I think it looks pretty good. One possible way to make it faster is in this part:

for ( int i = 0; i< k ; i++ ) {
for ( int j = i; j< k ; j++ ) {
int w = just_primes[i]+just_primes[j];
if ( w >= 1000000 && w <= 2000000 ) {
p = w - 1000000;
conjunct[p]++;
}
}
}


Notice that for each value of justprimes[i] you are currently testing all values of justprimes[j] and after this you are testing if the sum is in the desired interval.

One way to work around this is by using a two pointer method that tells us the biggest possible value j can take for any value of i, and also by breaking out of the loop as soon as j becomes to small.

int high = k-1;
for ( int i = 0; i< k ; i++ ) {
for ( int j = high; j>=i ; j-- ) {
int w = just_primes[i]+just_primes[j];
if(w< 1000000) break;
if ( w <= 2000000 ) {
p = w - 1000000;
conjunct[p]++;
}
else{
while( just_primes[i]+ just_primes[high] > 2000000 && high > 0){
high --;
}
}
}
}


This seems to give a 15% speed boost in my computer.