Optimize code with prime numbers

0

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()));
            }
        }
    }
}
    
asked by anonymous 17.09.2018 / 13:26

0 answers