首页 > 试题广场 >

素数伴侣

[编程题]素数伴侣
  • 热度指数：178049 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

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

输入:

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

输出:

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


数据范围： ，输入的数据大小满足

输入描述:
输入说明
1 输入一个正偶数 n 
2 输入 n 个整数


输出描述:
求得的“最佳方案”组成“素数伴侣”的对数。
示例1

输入

4
2 5 6 13

输出

2
示例2

输入

2
3 6

输出

0
算法知识视频讲解
开通博客
头像 xqxls
发表于 2021-12-07 15:50:02
题意整理。 输入N（N为偶数）个正整数，从其中挑选出若干对组成“素数伴侣”。 问怎么挑选，可以使得“素数伴侣”的对数最多。 如果两个正整数的和为素数，则这两个正整数称之为“素数伴侣”。 方法一（匈牙利算法） 1.解题思路 首先定义两个list容器，分别存储输入整数中的奇数和偶数。 然后利用匈牙 展开全文
去ta的博客 赞 (65) 回复(9) 收起
头像 前路漫漫且徐行
发表于 2021-03-01 19:44:36
import java.util.*; public class Main { //这里包含了判断素数的方法 //小技巧！！！素数不是偶数，那么和是素数的话就是奇数+偶数 //那么可以分成两堆,一堆偶数，一堆奇数 //匈牙利算法，先到先得 能让就让 //有机 展开全文
去ta的博客 赞 (58) 回复(10) 收起
头像 摸鱼学大师
发表于 2021-10-19 18:19:42
题目的主要信息： 若两个正整数的和为素数，则这两个正整数称之为“素数伴侣” 已知有NNN个数，NNN为偶数，从中挑选若干对组成“素数伴侣” 求最多能组成的“素数伴侣”对数 数组的范围是2-30000 我们首先要明白大于2的偶数不可能是素数，而我们的给的数组元素都是大于等于2的，因此两个数相加必定 展开全文
去ta的博客 赞 (45) 回复(2) 收起
头像 可导必连续^-^
发表于 2022-01-21 18:15:46
本题的思路是：如果是素数，一定是奇数和偶数结合（奇数）才有可能是素数，所以将需要配对的数分为两组，一组是奇数，一组是偶数，通过匈牙利算法求得最大的配对数 配对的思路是，可以把偶数和奇数当初来相亲的一些男女，首先一对男女相亲成功结婚了，然后另一个男生发现他和这个女生也合适，他就拆散这两个人，自己和这个 展开全文
去ta的博客 赞 (42) 回复(11) 收起
头像 日不落拓海海
发表于 2022-02-20 18:38:37
此题为匈牙利算法解决二分图最大匹配问题。我们可以把数据分为偶数，奇数两部分，然后进行配对（因为素数为一奇一偶的和）。 import math def isPrime(x): if x<=3: return x>1 for i in range(2, int 展开全文
去ta的博客 赞 (30) 回复(5) 收起
头像 waylau
发表于 2022-08-22 00:39:14
描述 若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的N（N为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴 展开全文
去ta的博客 赞 (28) 回复(0) 收起
头像 BoyangXu
发表于 2021-08-22 01:24:14
def is_prime(x):  # 判断是否是质数     for i in range(2, int(x ** 0.5) + 1): 展开全文
去ta的博客 赞 (27) 回复(1) 收起
头像 pullgon
发表于 2022-03-23 01:26:04
这道题和其他题难度不是一个级别的，看了别人的代码研究了一天才懂. import sys def is_prime(num): """判断是否为素数，偶数无需判断""" for i in range(3, int(num ** 0.5) + 2, 2): if num 展开全文
去ta的博客 赞 (17) 回复(2) 收起
头像 牛客830017178号
发表于 2021-05-15 14:18:26
写了1天..... 解答步骤写的比较详细 def getPrimes(n): """获取2~n之间的素数，用于对素数进行判断""" primes = [True for _ in range(n+1)] for i in range(2, n+1): if 展开全文
去ta的博客 赞 (16) 回复(0) 收起
头像 进阶110
发表于 2021-11-15 15:24:35
解题思路： 1.判断一个数是否为素数：在这里需要注意的是全部数判断会超时，所以选择半位数来判断可以节省时间。选用原理：一个数能被另一个数除尽，则这个数也能被它的2倍数除尽，一个数不能被另一个数除尽则也不能被它的2倍数除尽。 2.判断最大匹配数： 这个是参考已有的答案来的，一个列表里的数与另一个列表里 展开全文
去ta的博客 赞 (15) 回复(3) 收起

问题信息

查找 排序
难度：
209条回答 56730浏览

热门推荐

通过挑战的用户

查看代码

相关试题

素数伴侣

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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