普通网友 2021-11-11 20:55 采纳率: 42.9%
浏览 38
已结题

若两个正整数的和为素数,则这两个正整数称之为“素数伴侣”

题目描述
若两个正整数的和为素数,则这两个正整数称之为“素数伴侣”,如2和5、6和13,它们能应用于通信加密。现在密码学会请你设计一个程序,从已有的 N ( N 为偶数)个正整数中挑选出若干对组成“素数伴侣”,挑选方案多种多样,例如有4个正整数:2,5,6,13,如果将5和6分为一组中只能得到一组“素数伴侣”,而将2和5、6和13编组将得到两组“素数伴侣”,能组成“素数伴侣”最多的方案称为“最佳方案”,当然密码学会希望你寻找出“最佳方案”。

输入:

有一个正偶数 n ,表示待挑选的自然数的个数。后面给出 n 个具体的数字。

输出:

输出一个整数 K ,表示你求得的“最佳方案”组成“素数伴侣”的对数。

img

  • 写回答

1条回答 默认 最新

  • 从善若水 5G/6G通信领域优质创作者 2021-11-11 20:56
    关注
    
    #include<stdio.h>
    #include<vector>
    #include<string.h>
    using namespace std;
    vector<int> a;
    int book[210],match[210];
    int dfs(int);
    int isp[100000]={0};
    void su();
    int main()
    {
        int N,i,t;
        su();
        for(;scanf("%d",&N)!=EOF;)
        {
            a.clear();
            int sum=0;
            for(i=0;i<N;scanf("%d",&t),a.push_back(t),i++);
            memset(match,-1,sizeof(match));
            for(i=0;i<a.size();i++)
            {
                if(a[i]%2==0){
                    memset(book,0,sizeof(book)); book[i]=1;
                    if(dfs(i)) sum++;
                }
            }
            printf("%d\n",sum);
        }
    }
    
    int dfs(int x)
    {
        int i;
        for(i=0;i<a.size();i++)
            if(a[i]%2==1&&isp[a[i]+a[x]]==0&&book[i]==0)
            {
                book[i]=1;
                if(match[i]==-1||dfs(match[i]))
                {
                    //printf("%d->%d\n",a[x],a[i]);
                    match[i]=x;
                    match[x]=i;
                    return 1;
                }
            }
        return 0;
    }
    
    void su()
    {
        isp[0]=isp[1]=1;
        int i,j;
        for(i=2;i<100000;i++)
            if(isp[i]==0){
                for(j=2*i;j<100000;j+=i) isp[j]=1;
            }
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 11月20日
  • 已采纳回答 11月12日
  • 创建了问题 11月11日

悬赏问题

  • ¥15 vue3页面el-table页面数据过多
  • ¥100 vue3中融入gRPC-web
  • ¥15 kali环境运行volatility分析android内存文件,缺profile
  • ¥15 写uniapp时遇到的问题
  • ¥15 vs 2008 安装遇到问题
  • ¥15 matlab有限元法求解梁带有若干弹簧质量系统的固有频率
  • ¥15 找一个网络防御专家,外包的
  • ¥100 能不能让两张不同的图片md5值一样,(有尝)
  • ¥15 informer代码训练自己的数据集,改参数怎么改
  • ¥15 请看一下,学校实验要求,我需要具体代码