Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.2 kB
2
Indexable
public class PrimeCircle {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6};
        int count = backtrack(nums, new int[nums.length], new boolean[nums.length], 0);
        System.out.println(count);
    }

    private static int backtrack(int[] nums, int[] tempArray, boolean[] used, int index) {
        if (index == nums.length) {
            if (isPrime(tempArray[0] + tempArray[tempArray.length - 1])) {
                return 1;
            }
            return 0;
        } else {
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                if (used[i]) continue;
                if (index > 0 && !isPrime(tempArray[index - 1] + nums[i])) continue;
                tempArray[index] = nums[i];
                used[i] = true;
                count += backtrack(nums, tempArray, used, index + 1);
                used[i] = false;
            }
            return count;
        }
    }

    private static boolean isPrime(int n) {
        if (n <= 1) return false;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}