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)));
}
}
