首页 > 试题广场 >

素数伴侣

[编程题]素数伴侣
  • 热度指数：189012 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}定义两个正整数 a 和 b 是“素数伴侣”，当且仅当 a + b 是一个素数。
\hspace{15pt}现在，密码学会邀请你设计一个程序，从给定的 n 个正整数 \left\{a_1, a_2, \dots, a_n\right\} 中，挑选出最多的“素数伴侣”，你只需要输出挑选出的“素数伴侣”对数。保证 n 为偶数，一个数字只能使用一次。

输入描述:
\hspace{15pt}第一行输入一个正偶数 n \left(2 \leqq n \leqq 100\right) 代表数字个数。
\hspace{15pt}第二行输入 n 个正整数 a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 3 \times 10^4 \right) 代表给定的数字。


输出描述:
\hspace{15pt}输出一个整数，代表最多可以挑选出的“素数伴侣”的数量。
示例1

输入

4
2 5 6 13

输出

2

说明

\hspace{15pt}在这个样例中，2 和 5 可以组成一对素数伴侣，6 和 13 也可以组成一对素数伴侣。因此，最多可以挑选出 2 对素数伴侣。
示例2

输入

4
1 2 2 2

输出

1

说明

\hspace{15pt}在这个样例中，1 只能使用一次，与任意一个 2 组合均是“素数伴侣”。
示例3

输入

2
3 6

输出

0
算法知识视频讲解
添加回答
推荐
toraoh头像 toraoh
OK，我们把这个话题终结一下。

所有想着动态规划的，你们放弃吧，不是这么玩的。

考虑使用图论的方法来给这个题建模。
100个数看成100个点，如果这两个数加起来的和是素数，给这两个数中间连一条边。
之后，我们要选择尽可能多的边，要求这些边不共享端点。
——这个东西呢，叫做一般无向图的最大匹配。

但是，一般无向图的最大匹配，这个算法的难度，有点，大……
这个问题，合适的算法叫，带花树开花算法。
现场推完这么多，写一个正确的，有点不科学……

我们考虑再分析一下这个题
注意到，每个数的取值范围是[2,30000]
素数，除了2是偶数，其他是奇数——而现在不可能出现2了，所以我们只考虑奇数的素数
2个数的和是奇数，有什么情况呢？
只有奇数+偶数
所以，我们把这些数分成2堆——奇数和偶数，然后在他们中间，和是素数的，连上一条边，然后做匹配。
——肯定有人会说，你这个和前面的建图有什么本质不同的地方吗？
——是没有，但是我们说明了得到的图一定是二分图，这是有意义的。
因为对二分图的最大匹配，有一个简单很多的算法，匈牙利算法。

我们先说明一下，什么是二分图。
二分图就是，你可以把图上的点分成2堆，每堆之内的点不会有边，2堆之间，才可能连边。换句话说，一条边，必定连2个来自不同堆的点。
现在，对每条边，一定连一个奇数，一个偶数，点能按奇数和偶数分成两部分，刚好就是二分图嘛！

有关二分图匹配的匈牙利算法，具体请自行搜索，这里扯一下我个人对这个算法的理解。

外层，暴力考虑左边每个点
对枚举的每个左边的点，要找右边一个点来匹配。
那就是对左边的点，我们看他连出去的边，或者说，能连到的右边的点
有2种情况：
1、右边的点没人匹配——我直接贪心匹配上去
2、右边的点有人匹配——考虑把目前与这个右边的点 x 匹配的左边的点 pre[x]，重新匹配一个其他的点，如果成功了，那pre[x]原来匹配的点x就释放开了，我可以直接占领上去。
最后统计匹配成功多少个左边的点就行了。

匈牙利算法真的还是很短的，比你写一个红黑树轻松多了： 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> G[105];

bool flag[105];
int pre[105];

bool dfs(int k){
    int x;
    for(int i=0;i<G[k].size();i++){
        x=G[k][i];
        if (flag[x]) continue;
        flag[x]=true;
        if((pre[x]==0)||dfs(pre[x])){
            pre[x]=k;
            return true;
        }
    }
    return false;
}

bool isprime[80000];
int nums[105];

int main(){
    memset(isprime,1,sizeof(isprime));
    isprime[0]=isprime[1]=false;
    for(int i=4;i<80000;i+=2)isprime[i]=false;
    for(int i=3;i*i<80000;i+=2)
        if(isprime[i]){
            for(int j=i*i;j<80000;j+=2*i) isprime[j]=false;
        }
    int n;
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++){
            scanf("%d",&nums[i]);
        }
        for(int i=1;i<=n;++i){
            for(int j=i+1;j<=n;++j){
                if(isprime[nums[i]+nums[j]]){
                    (nums[i]&1)?G[i].push_back(j):G[j].push_back(i);
                }
            }
        }

        memset(pre,0,sizeof(pre));
        int ans=0;
        for(int i=1;i<=n;i++){
            memset(flag,false,sizeof(flag));
            if (dfs(i)) ans++;
        }
        printf("%d\n",ans);
        
        for(int i=1;i<=n;++i){
            G[i].clear();
        }
    }
    return 0;
}

（当然，你用网络流做二分图最大匹配，没人拦你。）

最后，给好学的人：
一般图匹配（牛刀）来做这个题（杀鸡）的代码：
带花树开花的模板 CopyRight Claris（http://www.lydsy.com/JudgeOnline/userinfo.php?user=Claris） 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N=510;
int n,m,x,y;vector<int>g[N];
namespace Blossom{
    int mate[N],n,ret,nxt[N],f[N],mark[N],vis[N];queue<int>Q;
    int F(int x){return x==f[x]?x:f[x]=F(f[x]);}
    void merge(int a, int b){f[F(a)]=F(b);}
    int lca(int x, int y){
        static int t=0;t++;
        for(;;swap(x,y)) if(~x){
            if(vis[x=F(x)]==t) return x;vis[x]=t;
            x=mate[x]!=-1?nxt[mate[x]]:-1;
        }
    }
    void group(int a, int p){
        for(int b,c;a!=p;merge(a,b),merge(b,c),a=c){
            b=mate[a],c=nxt[b];
            if(F(c)!=p)nxt[c]=b;
            if(mark[b]==2)mark[b]=1,Q.push(b);
            if(mark[c]==2)mark[c]=1,Q.push(c);
        }
    }
    void aug(int s, const vector<int>G[]){
        for(int i=0;i<n;++i)nxt[i]=vis[i]=-1,f[i]=i,mark[i]=0;
        while(!Q.empty())Q.pop();Q.push(s);mark[s]=1;
        while(mate[s]==-1&&!Q.empty()){
        int x=Q.front();Q.pop();
        for(int i=0,y;i<(int)G[x].size();++i){
                if((y=G[x][i])!=mate[x]&&F(x)!=F(y)&&mark[y]!=2){
                    if(mark[y]==1){
                        int p=lca(x,y);
                        if(F(x)!=p)nxt[x]=y;
                        if(F(y)!=p)nxt[y]=x;
                        group(x,p),group(y,p);
                    }else if(mate[y]==-1){
                        nxt[y]=x;
                        for(int j=y,k,l;~j;j=l)k=nxt[j],l=mate[k],mate[j]=k,mate[k]=j;
                        break;
                    }else nxt[y]=x,Q.push(mate[y]),mark[mate[y]]=1,mark[y]=2;
                }
            }
        }
    }
    int solve(int _n, const vector<int>G[]){
        n=_n;memset(mate, -1, sizeof mate);
        for(int i=0;i<n;++i) if(mate[i]==-1)aug(i,G);
        for(int i=ret=0;i<n;++i)ret+=mate[i]>i;
        printf("%d\n",ret);
        //for(int i=0;i<n;i++)printf("%d %d\n",i+1,mate[i]+1);
        return ret;
    }
}
bool isprime[80000];
int nums[105];
int main(){
    memset(isprime,1,sizeof(isprime));
    isprime[0]=isprime[1]=false;
    for(int i=4;i<80000;i+=2)isprime[i]=false;
    for(int i=3;i*i<80000;i+=2)
        if(isprime[i]){
            for(int j=i*i;j<80000;j+=2*i) isprime[j]=false;
        }
    while(~scanf("%d",&n)){
        for(int i=0;i<n;i++){
            scanf("%d",&nums[i]);
        }
        for(int i=0;i<n;++i){
            for(int j=i+1;j<n;++j){
                if(isprime[nums[i]+nums[j]]){
                    g[i].push_back(j);
                    g[j].push_back(i);
                }
            }
        }
        Blossom::solve(n,g);
        for(int i=0;i<n;++i){
            g[i].clear();
        }
    }
}

最后吐槽：华为这题出得都快和微软一个尿性了，二分图匹配和DAG上求支配者树，这个都不怎么好想出来的，硬生生想出来的，这个值得膜一膜，但是做出这个题的人，更多情况是，学过这个东西吧？
（你看这题的讨论区，多少人跳进了dp的大坑爬不出来？）
于是这是笔试题/面试题从一个极端走向另一个极端（从语言和库知多少，走向算法知识知多少 ） ？
编辑于 2016-09-10 13:03:39 回复(48)
C
胖乎乎的劳伦斯很高大头像 胖乎乎的劳伦斯很高大
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define Maxlength 100

/*素数伴侣
Case 1: 若为2个偶数和2个奇数的组合 直接否决
Case 2: 若到√n都未能被%,则为素数
*/
int rank(int matrix[Maxlength][Maxlength], int r, int c)
{
    //float a[N][M] = { {0,4,5,0,0,1,1,1,0},{-5,0,2,0,1,0,1,0,3},{7,2,0,0,-4,0,4,1,0},{-3,1,0,0,0,0,0,0,1},{2,-3,0,0,3,1,0,4,0} };
    int i, j, k;
    float temp;
    int rank_1 = 0, d = 0; //r表示秩，d表示当前正在哪一行。
    for (i = 0; i < c; i++)
    {
        k = d;                            /*a[i][i] a[i+1][i] ... a[n][i]中绝对值最大的行位置*/
        for (j = d + 1; j < r; j++)
            if (fabs(matrix[k][i]) < fabs(matrix[j][i]))
                k = j;
        if (k != d)                     /*交换第i行和第k行，行列式该变号*/
        {
            for (j = i; j < c; j++)
            {
                temp = matrix[d][j];
                matrix[d][j] = matrix[k][j];
                matrix[k][j] = temp;
            }
        }
        if (matrix[d][i] == 0)            /*当a[i][i]为零是时，行列式为零*/
        {
            continue;
        }
        else
        {
            rank_1 = rank_1 + 1;
            for (j = 0; j < r; j++)
            {
                if (j != d)
                {
                    temp = -1 * matrix[j][i] / matrix[d][i];
                    for (k = i; k < c; k++)
                        matrix[j][k] = matrix[j][k] + temp * matrix[d][k];
                }
            }
            temp = matrix[d][i];
            for (j = i; j < c; j++)
                matrix[d][j] = matrix[d][j] / temp;
        }
        d = d + 1;
        if (d >= r)
            break;
    }
    //printf("矩阵行的最简式为：\n");
    /*
    for (i = 0; i < r; i++)
    {
        for (j = 0; j < c; j++)
            printf("%.4f\t", matrix[i][j]);
        printf("\n");
    }
    printf("\n矩阵的秩R(A)=%d\n", rank_1);
    */
    return rank_1;
}




int main() {
    int a; //用来接收一个随机自然数
    //printf("请输入一个随机自然数n 范围1<=n<=100\n");
    //printf("自然数n:");
    scanf("%d", &a);
    int i = 0;
    int j = 0;
    int b[Maxlength]; //用来接收随机自然数的数组
    //printf("请输入n个自然数的值:可以用空格隔开\n");
    for (i; i < a; i++)
    {
        scanf("%d", &b[i]);
    }
    //printf("是否接收了a个自然数,打印效果如下:\n");
   
    int c[Maxlength / 2]; //用来接收奇数自然数的数组
    int d[Maxlength / 2]; //用来接收偶数自然数的数组
    //令i,j=0;
    i = j = 0;
    int k = 0;
    for (k; k < a; k++)
    {
        if (b[k] % 2 == 0)
        {
            d[j] = b[k];
            j++;
        }
        else
        {
            c[i] = b[k];
            i++;
        }
    }
    k = 0;
    //printf("是否分好了奇数和偶数数组,打印效果如下:\n");
    //printf("奇数数组C[Maxlength]:");
    //printf("\n");
    //printf("现在奇数数组有%d个元素,偶数数组有%d个元素\n", i, j);
    int count=0;
    int sum;
    int o = 0;
   
    //冒泡排序
    for (int n = 0; n < i; n++)
    {
        for (int o = n + 1; o < i; o++)
        {
            int temp = 0;
            if (c[n] > c[o])
            {
                temp = c[n];
                c[n] = c[o];
                c[o] = temp;
            }
        }
    }
    o = 0;
    for (int n = 0; n < j; n++)
    {
        for (int o = n + 1; o < j; o++)
        {
            int temp = 0;
            if (d[n] > d[o])
            {
                temp = d[n];
                d[n] = d[o];
                d[o] = temp;
            }
        }
    }
    o = 0;

    //printf("奇数数组C[Maxlength]:");
   
    //printf("\n");
   
   
    k = 0;
    //printf("\n");

    //问题转化为,现在找到所有可能的素数伴侣,这之中有重复的素数伴侣,需要删掉重复的素数伴侣
    //将能生成的素数伴侣对按奇偶分别放入不同的奇偶数组
    //删除奇偶数组重复元素,元素小的那个数组的元素个数即最佳奇偶素数伴侣对数

    int odd[Maxlength];  //用来接收
    int even[Maxlength]; //用来接收
    int array[Maxlength][Maxlength]; //二维数组
    for (int m = 0; m < i; m++)
    {
        for (int n = 0; n < j; n++)
        {
            if (d[n] == 0)
            {
                continue;
            }

            if (c[m] == 0)
            {
                break;
            }

            else
            {
                sum = c[m] + d[n];
                for (o = 2; o < sqrt(sum); o++)
                {
                    //printf("第%d次的sum值为:%d\n", o, sum);
                    if (sum % o == 0)
                        break;
                }

               
                if (o > sqrt(sum))
                {
                    count++;
                    //printf("第%d组 ", count);
                    //printf("奇数:%d ", c[m]);
                    //printf("偶数:%d ", d[n]);
                    //printf("合计:%d \n", sum);
                    odd[k] = c[m];
                    even[k] = d[n];
                    array[m][n] = 1;
                    k++;
                }
            }
        }
    }

    //将奇偶数组放入i*j的二维数组 (其中i为奇数数组元素个数 j为偶数数组元素个数)

    //printf("打印二维数组:\n");
    for (int m = 0; m < i; m++)
    {
        for (int n = 0; n < j; n++)
        {
            if (array[m][n] != 1)
            {
                array[m][n] = 0;
                //printf("%d ", array[m][n]);
            }
        }
    }



    //现在k的值为全部素数伴侣对数的值 此时k=count      
    //删除 奇偶数组重复值
    for (k = 0; k < count; k++)
    {
        for (int u = k + 1; u < count; u++)
        {
            if (odd[k] == odd[u])
                odd[u] = 0;
        }
    }

    for (k = 0; k < count; k++)
    {
        for (int p = k + 1; p < count; p++)
        {
            if (even[k] == even[p])
                even[p] = 0;
        }
    }

    int count_1 = 0;
    int count_2 = 0;

    for (k = 0; k < count; k++)
    {
        if (odd[k] != 0)
            count_1++;
        if (even[k] != 0)
            count_2++;
    }

    count = rank(array, i+1, j);
    //printf("count_1:%d\n", count_1);
    //printf("count_2:%d\n", count_2);
    //count = count_1 < count_2 ? count_1 : count_2;
    printf("%d", count);
    return 0;
}
发表于 2023-03-10 20:36:38 回复(1)
C
牛客219878930号头像 牛客219878930号
我提出一个想法给大家哈，用线性代数的方法，就是先按照奇数偶数分组，然后计算出一个组合表 交叉点为1表示和为素数 0则不是，然后这个矩阵的秩其实就是最多组合的个数，因为行交换和列交换对这个表来说都不会有影响，但是注意的是要先剔除相同的数值，不然会导致结果比正确结果小1.
发表于 2022-07-18 09:33:26 回复(1)
提交观点

问题信息

查找 排序
难度：
3条回答 57956浏览

热门推荐

通过挑战的用户

查看代码

相关试题

素数伴侣

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号