题解 | #素数伴侣#

超时了呜呜呜

#include <math.h>
#include <stdio.h>

int maxcnt = 0;
/*int max_pa[1000][2] = {0};
int pa[1000][2] = {0};*/

int isprime(int x, int y) {
    int sum = x + y;
    if (sum == 2 || sum == 3) {
        return 1;
    }

    for (int i = 2; i * i <= sum; i++) {
        if (sum % i == 0) {
            return 0;
        }
    }
    return 1;
}
void DFS(int data[], int n, int cnt) {
    if (n == 2) {
        if (isprime(data[0], data[1])) {
           /* pa[cnt][0] = data[0];
            pa[cnt][1] = data[1];*/
            cnt++;
            
        }
        if (maxcnt < cnt) {
            maxcnt = cnt;
            /*for (int i = 0; i < cnt; i++) {

                max_pa[i][0] = pa[i][0];
                max_pa[i][1] = pa[i][1];
            }*/
        }

        return;

    } else {
        for (int j = 1; j < n; j++) {
            int data2[n - 2];
            int index = 0;
            for (int i = 1; i < n; i++) {
                if (i != j) {
                    data2[index++] = data[i];
                }
            }

            if (isprime(data[0], data[j])) {

               /* pa[cnt][0] = data[0];
                pa[cnt][1] = data[j];*/
                cnt++;
                DFS(data2, n-2, cnt);
                cnt--;

            }
            else
                DFS(data2, n-2, cnt);
        }
    }
}
int main() {
    int n = 0;

    scanf("%d", &n);
    int data[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &data[i]);
    }

    DFS(data, n, 0);

    printf("%d\n", maxcnt);

    /*for (int i = 0; i < maxcnt; i++) {
        printf("%d %d\n", max_pa[i][0], max_pa[i][1]);
    }*/
}