I have the following problem: I need a program that receives a positive even number from the input and forms a "wheel" with these numbers, so that:
- All numbers from 1 to n are used in the circle only once.
- The sum of two consecutive numbers is a prime number.
- The sum of a number with what is diametrically opposite to it is also a prime number.
For example, an 18-number wheel would be displayed as follows in vector form: 1 6 7 16 15 8 5 12 11 18 13 10 3 4 9 14 17 2.
I have the following code, but if you run it, you will see that you can leave running and take a trip to visit the relatives who live far away, and maybe when you come back it will have resulted in something. I need to optimize it and, if possible, run in less than a minute:
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()));
}
}
}
}