Tenho o seguinte problema: preciso de um programa que receba de entrada um número par positivo e forme uma “rodinha” com esses números, de forma que:
-Todos os números de 1 a n sejam usados no círculo somente uma vez.
-A soma de dois números consecutivos seja um número primo.
-A soma de um número com o que está diametralmente oposto a ele também seja um número primo.
Por exemplo, uma rodinha de 18 números seria exibida da seguinte maneira em forma de vetor:
1 6 7 16 15 8 5 12 11 18 13 10 3 4 9 14 17 2.
Eu tenho o seguinte código, porém se vocês rodarem ele, verão que podem deixar rodando e fazer uma viagem para visitar os parentes que moram longe, e talvez, quando você voltar, terá resultado em alguma coisa. Preciso otimizar ele e, se possível, rodar em menos de um minuto:
‘’’
import java.sql.Date;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Vector;
import javax.swing.JOptionPane;
/**
* Desafio 5
*
* @author Conan,O Barbaro
*
*/
public class QuintoDesafio {
private static int j;
private static int k;
static final long longLimit = (long) 500;
private static Vector primos = new Vector();
public static void main(String[] args)
{
long inicio = System.currentTimeMillis();
ArrayList lista = new ArrayList();
ArrayList<Long> primos = new ArrayList<Long>();
long longNumber=5;
int intNext=0, intIndex=0;
double doubleSquareRoot=0.0;
primos.add(new Long(2));
primos.add(new Long(3));
do {
intNext = 0;
doubleSquareRoot = Math.sqrt(longNumber);
while ((double) primos.get(++intNext)<doubleSquareRoot && (longNumber%primos.get(intNext))!=0);
if ((double) primos.get(intNext)>doubleSquareRoot) primos.add(new Long(longNumber));
longNumber+=((longNumber%3==2)?2:4);
} while (longNumber<longLimit);
String n = JOptionPane.showInputDialog( "Informe n (par) ");
int ene = Integer.parseInt( n );
for ( int i=1; i <= ene; i++ ) {
lista.add( new Integer(i) );
}
permuta(lista, 0);
long fim = System.currentTimeMillis();
System.out.println(new SimpleDateFormat("ss.SSS").format(new Date(fim - inicio)));
}
static void permuta(ArrayList arr, int k){
boolean passou = true;
for(int i = k; i < arr.size(); i++){
java.util.Collections.swap(arr, i, k);
permuta(arr, k+1);
java.util.Collections.swap(arr, k, i);
}
if (k == arr.size() -1){
int metade = arr.size()/2;
for ( int j=0; j<arr.size(); j++ ) {
int um = (int) arr.get(j);
int dois;
if ( j+1 == arr.size() ) {
dois = (int) arr.get(0);
} else {
dois = (int) arr.get(j+1);
}
Integer numteste = new Integer( um+dois );
if ( !primos.contains( numteste )) {
passou = false;
}
}
for ( int j=0; j<metade; j++ ) {
int um = (int) arr.get(j);
int dois = (int) arr.get(j+metade);
Integer numteste = new Integer( um+dois );
if ( !primos.contains( numteste )) {
passou = false;
}
}
if ( passou ) {
System.out.println(java.util.Arrays.toString(arr.toArray()));
}
}
}
}
‘’’
Eu fiz outro código seguindo uma lógica de embaralhar a lista até que se chegasse na solução, mas ela também demora demais para rodar e tem vezes que não chega no resultado. Se alguém puder me dar uma luz sobre este problema, fico agradecido.
