题解 | #素数伴侣#

#include <cmath>
#include <iostream>
#include <ratio>
#include <vector>
using namespace std;

bool isSu(int x){
    for(int i=2;i<=(int)sqrt(x);++i){
        if(x%i==0)
            return false;
    }
    return true;
}

int result=0;
vector<pair<int,int>> path;

void dfs(vector<int>& num,vector<int>& used,int cur){
    for(int i=0;i<num.size();++i){
        if(used[i]==0){
            used[i]=1;
            for(int j=0;j<num.size();++j){
                if(used[j]==0&&isSu(num[i]+num[j])){
                    used[j]=1;
                    path.push_back({num[i],num[j]});
                    int n=path.size();
                    result=max(result,n);
                    dfs(num,used,cur+2);
                    path.pop_back();
                    used[j]=0;
                }
            }
            used[i]=0;
        }
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> num(n);
    for(int i=0;i<n;++i)
        cin >> num[i];
    vector<int> used(n,0);
    dfs(num,used,0);
    cout << result;
}
// 64 位输出请用 printf("%lld")