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

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

题目描述
若两个正整数的和为素数,则这两个正整数称之为“素数伴侣”,如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 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题