题解 | #素数伴侣# 贪心

1. 每次先统计每个数能够和几个数成功匹配
2. 把不能匹配的数删去，然后找到匹配方法最少的数 X
3. 找出能和X匹配的数中匹配方法数最少的数Y
4. 把X、Y作为一对匹配，然后删除X、Y，继续寻找下一对匹配的数直到没有数可以匹配就结束。

• 复杂度为 N^3

#include <bits/stdc++.h>
using namespace std;
int n,minpair=1,ans=0;
int A[110]={0},B[110]={0};
int isprime[60001]={0};

int main() {
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>A[i];
    }
    for(int i=2;i<=60000;i++){
        isprime[i]=1;
    }
    for(int i=2;i<=60000;i++){
        if(isprime[i]){
            //cout<<i<<endl;
            for(int j=2*i;j<=60000;j+=i){
                isprime[j]=0;
            }
        }
    }

    while(1){
        int k=0;
        minpair=0;
        B[0]=1e9;
        for(int i=1;i<=n;i++){
            B[i]=0;
        }
        for(int i=1;i<=n;i++){//统计所有数的匹配方法数
            k+=A[i];
            if(A[i]==0) continue;//已经匹配过的数为0,跳过
            for(int j=i+1;j<=n;j++){
                if(A[j]==0) continue;
                if(isprime[A[i]+A[j]]){
                    B[i]++;
                    B[j]++;
                }
            }
            if(B[i]==0){//无法匹配,直接删除
                A[i]=0;
                continue;
            }
            if(B[minpair]>B[i]) minpair=i;
        }
        if(minpair==0) break;
        int minpair2=0;
        for(int i=1;i<=n;i++){
            if(A[i]!=0&&i!=minpair && isprime[A[i]+A[minpair]]){
                if(B[minpair2]>B[i]) minpair2=i;
            }
        }
        ans++;
        A[minpair]=0;
        A[minpair2]=0;

    }
    cout<<ans;
    return 0;
}