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 &lt; 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&lt;2000000; i++ ) {
            primes[i] = i+1;
        }

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

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

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

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

        int p;
        for ( int i = 0; i&lt; k ; i++ ) {
            for ( int j = i; j&lt; k ; j++ ) {
                int w = just_primes[i]+just_primes[j];
                if ( w &gt;= 1000000 &amp;&amp; w &lt;= 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&lt;1000001 ; i++ ) {
            if ( conjunct[i] &gt;= big1 ) {
                big3 = big2;
                big2 = big1;
                big1 = conjunct[i];
                n3 = n2;
                n2 = n1;
                n1 = i;
            } else {
                if ( conjunct[i] &gt;= big2 ) {
                    big3 = big2;
                    big2 = conjunct[i];
                    n3 = n2;
                    n2 = i;
                } else {
                    if ( conjunct[i] &gt;= 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
I think it looks pretty good. One possible way to make it faster is in this part:

for ( int i = 0; i&lt; k ; i++ ) {
    for ( int j = i; j&lt; k ; j++ ) {
        int w = just_primes[i]+just_primes[j];
        if ( w &gt;= 1000000 &amp;&amp; w &lt;= 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&lt; k ; i++ ) {
        for ( int j = high; j&gt;=i ; j-- ) {
            int w = just_primes[i]+just_primes[j];
            if(w&lt; 1000000) break;
            if ( w &lt;= 2000000 ) {
                p = w - 1000000;
                conjunct[p]++;
            }
            else{
                while( just_primes[i]+ just_primes[high] &gt; 2000000 &amp;&amp; high &gt; 0){
                    high --;
                }
            }
        }
    }


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