# Untitled

unknown
plain_text
15 days ago
1.7 kB
0
Indexable
Never
```class Solution {
static int[] visited;
static int[] rings;
static int[] prime;
static int[] primeRing;
static Scanner sc;
static int sum = 0;

public static void main(String args[]) throws Exception {
sc = new Scanner(System.in);
int T;
T = sc.nextInt();

for (int test_case = 1; test_case <= T; test_case++) {

int n = sc.nextInt();
visited = new int[n];
rings = new int[n];
prime = new int[100];

sum = 0;

// input matrix
for (int i = 0; i < n; i++) {
rings[i] = sc.nextInt();
visited[i] = 0;
}

caculatePrime();
visited[0] = 1;
backtrack(0, 0);

System.out.println("Case #" + test_case + ": " + sum);
visited = null;
rings = null;
}
}

private static void caculatePrime() {
for (int i = 0; i < rings.length; i++) {
for (int j = i + 1; j < rings.length; j++) {
int sum = rings[i] + rings[j];
if (isPrime(sum)) {
prime[sum] = 1;
}
}
}
}

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

private static void backtrack(int node, int prev) {// i la dinh dang xet
if (node == rings.length - 1) {
if (prime[rings[prev] + rings[0]] == 1) {
sum++;
}
return;
}
for (int i = 1; i < rings.length; i++) {
if (visited[i] == 0) {
if (prime[rings[prev] + rings[i]] == 1) {
visited[i] = 1;
backtrack(node + 1, i);
visited[i] = 0;
}
}
}
}

private static boolean isOK(int i) {
for (int j = 0; j < rings.length; j++) {
if (visited[j] == 0) {
int sumRings = rings[i] + rings[j];
if (sumRings % 2 != 0) {
return true;
}
}
}
return false;
}
}```