Conjuntos solução da conjectura de Goldbach

[SolaDeCoro]

Olá pessoas. Recebi um desafio baseado na conjectura de Goldbach. Como vocês devem saber, essa teoria diz que todo número par acima de 2 pode ser representado pela soma de dois números primos. Exemplo: 12 (5, 7), onde 5 + 7 = 12. Porém a maioria dos números maiores tem mais do que uma solução possível, por exemplo o 26, que pode ser representado com o seguinte conjunto solução: {(3, 23),(7, 19),(13, 13)}. O meu objetivo é escrever um programa que encontre os três números entre 1000000 e 2000000 que possuem os maiores conjuntos solução, ou seja, os três números pares nesse intervalo que podem ser representados pelo maior número de somas de dois números primos. A resposta é obtida pelo algoritmo abaixo, o problema é que ele demora 13 segundos para rodar, e preciso de algo bem mais rápido do que isso. Não sei por onde começar esta otimização, alguém tem alguma ideia?

import java.sql.Date;
import java.text.SimpleDateFormat;

/**
 * Desafio JB1
 *
 * @author Conan,OBarbaro
 *
 */

public class SegundoDesafio {

    private static int j;
    private static int k;
    private static int [] primos;
    private static int [] soprimos;
    private static int [] conjuntos;

    public static void main(String[] args)
    {

        long inicio = System.currentTimeMillis();

        // Algoritmo do crivo de Erast?stenes
        primos = new int[2000000];
        for ( int i=0; i<2000000; i++ ) {
            primos[i] = i+1;
        }

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

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

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

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

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

        int maior1 = 0;
        int maior2 = 0;
        int maior3 = 0;
        int n1 = 0;
        int n2 = 0;
        int n3 = 0;

        for ( int i = 0; i<1000001 ; i++ ) {
            if ( conjuntos[i] >= maior1 ) {
                maior3 = maior2;
                maior2 = maior1;
                maior1 = conjuntos[i];
                n3 = n2;
                n2 = n1;
                n1 = i;
            } else {
                if ( conjuntos[i] >= maior2 ) {
                    maior3 = maior2;
                    maior2 = conjuntos[i];
                    n3 = n2;
                    n2 = i;
                } else {
                    if ( conjuntos[i] >= maior3 ) {
                        maior3 = conjuntos[i];
                        n3 = i;
                    }
                }
            }
        }


        System.out.println( "Maior conjunto: " + (1000000 + n1) + " " + maior1 + " pares" );
        System.out.println( "conjunto Massa: " + (1000000 + n2) + " " + maior2 + " pares" );
        System.out.println( "Barrichelo    : " + (1000000 + n3) + " " + maior3 + " pares" );

        long fim  = System.currentTimeMillis();
        System.out.println(new SimpleDateFormat("ss.SSS").format(new Date(fim - inicio)));


    }

}

[lvbarbosa]

Cara, a lógica pra resolver esse problema é exatamente a mesma do sistema monetário. Você tem um conjunto de números e deseja saber a respeito das possíveis combinações de soma deles. Resolve com programação dinâmica e tabulação (Memoization).

[SolaDeCoro]

Mas aí preciso passar um vetor com os números primos possíveis nesse intervalo? Enfim, não sei como aplicar essa técnica nesse caso.

[peczenyj]

vamos la

antes de começar a otimizar vc precisa saber quanto tempo vc gasta com cada etapa, não adianta otimizar uma parte que ja é rapida

eu vou assumir q gerar os números primos desse jeito é rápido. Eu gosto do Crivo de Sundaram, onde se vc quer encontrar todos os primos ate X, vc vai testar se X eh divisível por todos os números entre 2 e raiz quadrada de sort(X) pois na primeira divisão vc vai interromper o loop, ai basta fazer um loop de números impares entre 3 e X ( adiciona o 2 no começo afinal esse numero é safadyto )

se gerar os números primos ta ok, vamos ao seu algoritmo. vc quer descobrir os 3 números entre 1000000 e 2000000 que possuem os maiores conjuntos de soluções.

pois bem. vc so precisa verificar os números pares, e isso te da uma super vantagem.

vamos assumir que 2000000 eh o seu máximo. vc nao precisa verificar números impares e menores que 1000000 entao

int MAX = 2000000;
int MIN = 1000000;
for(int n = MIN; n < MAX ; n += 2) {
  int c = calculaQuantidadeDeCombinacoes( n );
  // agora vc quer armazenar o par n,c em algum lugar.
  // e encontrar os 3 n que tem maior c
}

uma coisa q vc pode tentar eh pre-calcular uma tabela com a soma de primos

int MAX = 2000000;
int MIN = 1000000;
for(int i = 0; i < quantidadeDePrimos;i++) { 
   for(int j=i; j < quantidadeDePrimos;j++) {
     int par = primos[i] + primos[j];
     // veja se par esta entre o máximo e o mínimo
     tabelaDeCombinacoes[ par /* - MIN ? */ ]++;
     // ou outra estrutura de dados
   }
}

e ai trabalha um pouco isso. talvez uma estrutura de dados que ja insira ordenado por algum critério ajude

eh um bom problema, boa sorte

[lvbarbosa]

Se quiser seguir nesse método, faz assim:

1. Acha os números primos e coloca num array ordenado;
2. Pra cada número que você quer testar, percorre o array de primos. Pra cada primo, subtrai ele do número que você tá testando e faz uma busca binária do resultado da subtração no array de primos. Se você encontrar, significa que é uma solução. Adiciona 1 no contador de soluções;
3. Retorna o contador de soluções.

Essa solução é O(n logn).