5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ How are 981980, 951950, and 995630 "between 1,000,000 and 2,000,000"? \$\endgroup\$ – גלעד ברקן Apr 26 at 14:59
  • \$\begingroup\$ Good point, he needs to add 10^6 to the number first. \$\endgroup\$ – Jorge Fernández Apr 26 at 15:01
4
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.