(UVA) Prime Ring Problem - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=465

The solution below is using backtracking.

Once the maximum sum between two adjacent nodes will be 31, it is pre-calculated all the prime numbers until 40. Then, every time that we need to check if the sum of two nodes is prime, we only need to check if the result is in the sequence of prime numbers.


import java.io.*;
import java.util.*;

class Main {
    public static int qty;
    public static HashSet<Integer> considered;
    public static ArrayList<Integer> seq;
    public static HashSet<Integer> prime;
    public static BufferedWriter bw;
   
    public static void rec(int number) throws NumberFormatException, IOException {
        if (considered.size() == qty && prime.contains(number+1)) {
            for (int i = 0; i < qty-1; i++) {
                bw.write(seq.get(i) + " ");
            }
            bw.write(seq.get(qty-1)+"\n");
        }
       
        for (int i = 1; i <= qty; i++) {
            if (i == number || considered.contains(i) || !prime.contains(number+i)) {
                continue;
            }
            considered.add(i);
            seq.add(i);
            rec(i);
            seq.remove(seq.size()-1);
            considered.remove(i);
        }
    }
   
    public static boolean isPrime(int n) {
        for (int i = 2; i < n; i++) {
            if (i == n) {
                continue;
            }
            if (n%i == 0) {
                return false;
            }
        }
       
        return true;
    }
   
    public static void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        int numCase = 0;
        while (sc.hasNext()) {
            if (numCase >= 1) {
                bw.write("\n");
            }
           
            qty = sc.nextInt();
           
            prime = new HashSet<>();
            for (int i = 2; i < 40; i++) {
                if (!isPrime(i)) {
                    continue;
                }
                prime.add(i);
            }
           
            bw.write("Case " + ++numCase + ":\n");
            considered = new HashSet<>();
            considered.add(1);
            seq = new ArrayList<>();
            seq.add(1);
            rec(1);
        }
       
        bw.flush();
        bw.close();
                               
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}