最大组数的“素数伴侣”

2024-05-13 01:04
文章标签 最大 素数 伴侣 组数

本文主要是介绍最大组数的“素数伴侣”，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

若两个正数之和为素数，则这两个数称之为“素数伴侣”。利用此特性找出给定数组中最大的“素数伴侣”对数。

(笔记模板由python脚本于2024年05月11日 18:17:40创建，本篇笔记适合熟悉基本编程且了解素数的coder翻阅)

【学习的细节是欢悦的历程】

  • Python 官网：https://www.python.org/

  • Free：大咖免费“圣经”教程《 python 完全自学教程》，不仅仅是基础那么简单……
    地址：https://lqpybook.readthedocs.io/

  自学并不是什么神秘的东西，一个人一辈子自学的时间总是比在学校学习的时间长，没有老师的时候总是比有老师的时候多。
            —— 华罗庚

  • My CSDN主页、My HOT博、My Python 学习个人备忘录
  • 好文力荐、 老齐教室
等风来，不如追风去……
若两个正数之和为素数
最大组数的“素数伴侣”
(则这两个数称之为“素数伴侣”)

本文质量分：

【 97 97 97 】

本文地址： https://blog.csdn.net/m0_57158496/article/details/138750188

CSDN质量分查询入口：http://www.csdn.net/qc

目 录

  • ◆ 素数伴侣
    • 1、题目描述
    • 2、算法解析
      • 2.1 素数判定函数
      • 2.2 手撕“素数伴侣”组合
      • 2.3 求助itertools.combinations()
      • 2.4 最佳“素数伴侣”方案
    • 3、我关于素数的学习笔记
    • 4、完整源码(Python)

◆ 素数伴侣


1、题目描述


  • 题目描述图片
    在这里插入图片描述
    题目文本：
      若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的N (N为偶数)个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数: 2, 5, 6, 13，如果将5和6分为一组，只能得到一组“素数伴侣”；而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣"最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案"。.
     
    输入:
    有一个正偶数n,表示待挑选的自然数的个数。后面给出n个具体的数字。
     
    输出:
    输出一个整数K，表示你求得的“最佳方案组成素数伴侣的对数。
     
    数据范围: 1 ≤ n ≤ 100 1 ≤ n ≤ 100 1≤n≤100 ，输入的数据大小满足 2 < v a l ≤ 30000 2 < val ≤ 30000 2<val≤30000
     
    输入描述：
    1. 输入一个正偶数n
    2. 输入n个整数
     
    输出描述：
    求得的“最佳方案”组成素数伴侣的对数
     
    示例1
    输入:
    4
    2 5 6 13
    输出:
    2


    示例2
    输入:
    2
    3 6
    输出:
    0


回页目录

2、算法解析


  要输出“素数伴侣”的最大组数，得先要晓得，给定数组可以组合出来的“素数伴侣”组合对数(不重复)。然后分别从给定数组中取出“素数伴侣”，并记录取出的组数，与保存的最大组数比较，保存大者。测试完所有可能的组合取数方案，最后输出保存的“最大组数”变量值就好了。

  我觉得最大的难点在于遍历所有可能的组合方案，我感觉像“动态规划”，但我又是算法白痴，更不要说掌握“动态规划”算法模板，我连其概念都是一团浆糊。😂😂所以我无法可想的情形下，选择手撕🤨经过近两小时的“推敲”，终于获得了题目中的两个样例的预期输出。😋终于是“不负时光”，但还应该有更多样例试码。

  学习搭子“甩过来一个“复杂”样例：25606, 9056, 17585, 9754, 29060, 978, 3156, 9997, 13286, 3419, 18853, 5325, 1580, 292, 24811, 943, 18898, 6507, 6270, 7296, 15538, 20251, 28206, 10001, 818, 3953, 993, 15744, 8489, 20700, 18853, 24969，预期输出：15。


  我忐忑上码，紧张、期待……


  手机屏幕“眨眼”的瞬间，我感觉好漫长！终于，如期跳出了 15 15 15。🙏🙏🙏

  • 代码运行效果截屏图片在这里插入图片描述


  但这不一定就证明我的代码没有 b u g bug bug，得通过更多的样例来验证。


  • 接下来，实施解题：
     
    1、要确定“素数伴侣”，得有素数判定的代码。简单！ n e w new new一个。
     
    2、找出给定数组中所有不重复的“素数伴侣”组合。可以for手撕，也可以托儿itertools.combinations()(Python御用不重复排序组合工具函数)。
     
    3、设计、统计能取出最多组数“素数伴侣”的方案，输出最大组数。


回页目录

2.1 素数判定函数


Python代码


def isPrime(num: int) -> bool:''' 素数判定 '''if num < 2:return False # 小于2的都不是素数if num == 2 or num == 3: return True # 2和3都是素数elif num%2 == 0 or num%3 == 0: return False # 剔除2、3的倍数for i in range(5, int(num**0.5)+1, 6): # 只检查6k±1的自然数if num%i == 0 or num%(i+2) == 0:  return False # 大于5的素数都满足6k±1的形式，6k形式的数一定是合数return True # 经过前面的排查，就只剩素数了
  • 验证
    在这里插入图片描述
      素数判定算法，详见往期笔记，点击蓝色文字跳转翻阅。


回页目录

2.2 手撕“素数伴侣”组合


Python代码


partners = [] # 素数伴侣集合
for i in range(n):for j in range(i+1, n):if isPrime(nums[i]+nums[j]):partners += [(nums[i], nums[j])] # 追加素数伴侣

  • 代码解读
     
      这段代码的目的是找到列表 nums 中所有能够组成素数和的数字对。 isPrime 用于检查两个数字和是否为素数。
     
    让我们逐步分析代码：
    1.  partners = []：初始化一个空列表 partners，用于存储所有能够组成素数和的数字对（即“素数伴侣”）。
    2.  外层循环 for i in range(n):：遍历列表 nums 中的所有数字。n 应该是列表 nums 的长度。
    3.  内层循环 for j in range(i+1, n):：再次遍历列表 nums，但这次从 i+1 开始，避免重复检查和自身以及之前的数字的组合。
    4.  if isPrime(nums[i]+nums[j]):：检查 nums[i] 和 nums[j] 的和是否为素数。如果是，进入下一步。
    5.  partners += [(nums[i], nums[j])]：将这个“素数伴侣”的数字对添加到 partners 列表中。
     
      最终，partners 列表中将包含所有可能的“素数伴侣”数字对。

  • 验证
    在这里插入图片描述
    在这里插入图片描述


回页目录

2.3 求助itertools.combinations()


Python代码


from itertools import combinations # 加载不重复排序组合函数
print(f"\n素数伴侣：\n{partners = }\n(for嵌套手撕)\n\npartners = {[i for i in combinations(nums, 2) if isPrime(sum(i))]}\n(调用combinations())")
  • 验证
    在这里插入图片描述
    在这里插入图片描述


回页目录

2.4 最佳“素数伴侣”方案


Python代码


# 从输入数组中中删除已取组合数字
def myremove(partner: tuple) -> None:a, b = partnerif a in c and b in c:c.remove(a)c.remove(b)return 1 # 成功取数返回1return 0 # 取数不成功返回0# 找最佳组合
result: int = 0 # 最后输出的最大组数
for i in partners: # m外层循环是从输入数组中取第一个组合k: int = 0 # 当前取法计数器c = nums[:] # 输入数组副本k += myremove(i) # 计数d = partners[:] # 所有合规组合副本d.remove(i) # 删除外层循环的那一组for j in d: # 遍历其余合规组合k += myremove(j) # 在输入数组中查找并计数result = max(result, k) # 记录最大数量的素数伴侣组合数print(f"\n输出：{result}")

  • 代码解析
     
      这段代码的目的是找到列表 nums 的最大“素数伴侣”组合数。

    让我们逐步分析代码：
    1.  myremove(partner: tuple) -> None：这个函数，用于从输入数组 c 中删除一个给定的素数伴侣组合 partner。如果组合中的两个数字都存在于数组 c 中，则删除它们并返回 (表示成功取数)，否则返回 0(表示取数不成功)。
    2.  result: int = 0：初始化一个变量 result，用于存储最终的最大素数伴侣组合数。
    3.  外层循环 for i in partners:：遍历 partners 列表中的所有素数伴侣组合。
    4.  k: int = 0 和 c = nums[:]：初始化一个计数器 k，用于记录当前取法中的素数伴侣组合数。同时，创建一个输入数组 nums 的副本 c，用于在每次迭代中模拟移除操作。
    5.  k += myremove(i)：尝试从副本数组 c 中移除当前的外层循环素数伴侣组合 i，并更新计数器 k。
    6.  d = partners[:] 和 d.remove(i)：创建 partners 列表的副本 d，并从副本中移除当前的外层循环素数伴侣组合 i。
    7.  内层循环 for j in d:：遍历剩余的素数伴侣组合副本 d。
    8.  k += myremove(j)：用myremove函数返回值，并更新计数器 k的值。
    9.  result = max(result, k)：更新最终的最大素数伴侣组合数 result。
    10.  print(f"\n输出：{result}")：输出最终的最大素数伴侣组合数。

  这段代码的时间复杂度较高，因为它使用了嵌套循环来遍历所有可能的素数伴侣组合。


  • 验证
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述


回页目录

3、我关于素数的学习笔记


  • 素数判定算法优化
    地址：https://blog.csdn.net/m0_57158496/article/details/138725500
    浏览阅读：783
    点赞：9 收藏：22 
     
  • 最大组数的“素数伴侣”
    地址：https://blog.csdn.net/m0_57158496/article/details/138750188
    浏览阅读：749
    点赞：18 收藏：8 
    (本篇笔记于2024-05-12 11:29:35首次发布，最后修改于2024-05-12 21:54:50)
     
  • 5个写自定义函数小练习
    地址：https://blog.csdn.net/m0_57158496/article/details/134321362
    浏览阅读：529
    点赞：2 收藏：2 评论：2
    (本篇笔记于2023-11-10 00:37:19首次发布，最后修改于2023-11-10 22:48:13)
     
  • 幸运素数(找出给定区间的所有幸运素数)
    地址：https://blog.csdn.net/m0_57158496/article/details/134346918
    浏览阅读：352
    点赞：1 收藏：2 
    (本篇笔记于2023-11-11 12:59:47首次发布，最后修改于2023-11-11 22:30:33)
     
  • 素数查找(def自定义函数练习)
    地址：https://blog.csdn.net/m0_57158496/article/details/118497087
    浏览阅读：344
     


  • 回页目录

    4、完整源码(Python)

    (源码较长，点此跳过源码)

    #!/sur/bin/nve python 
# coding: utf-8 
from itertools import combinationsdef isPrime(num: int) -> bool:''' 素数判定 '''if num < 2:return False # 小于2的都不是素数if num == 2 or num == 3: return True # 2和3都是素数elif num%2 == 0 or num%3 == 0: return False # 剔除2、3的倍数for i in range(5, int(num**0.5)+1, 6): # 只检查6k±1的自然数if num%i == 0 or num%(i+2) == 0:  return False # 大于5的素数都满足6k±1的形式，6k形式的数一定是合数return True # 经过前面的排查，就只剩素数了k = 200
from time import time
start = time()
rr = [i for i in range(k) if isPrime(i)]
#print(f"\n{'':~^41}\n{k}以内的素数：\n{' '.join(map(str, rr))}\n\n有{len(rr)}个，用时用时{time()-start:.4f}秒\n{'':~^41}\n")print(f"\n输入：")
if (in_data := '\n'.join([input().strip() for i in 'ab'])) == '\n':in_data = '''4
2 5 6 13'''n, nums = in_data.split('\n')
n, nums = int(n), list(map(int, nums.split()))
#print(f"\n{n = }\n{nums = }\n")# 测试用例
#nums = [25606, 9056, 17585, 9754, 29060, 978, 3156, 9997, 13286, 3419, 18853, 5325, 1580, 292, 24811, 943, 18898,6507, 6270, 7296, 15538, 20251, 28206, 10001, 818, 3953, 993, 15744, 8489, 20700, 18853, 24969]  # 预期输出 15
n = len(nums)
print('\n测试用例：', str(nums)[1:-1])partners = [] # 素数伴侣集合
for i in range(n):for j in range(i+1, n):if isPrime(nums[i]+nums[j]):partners += [(nums[i], nums[j])] # 追加素数伴侣from itertools import combinations # 加载不重复排序组合函数
#print(f"\n素数伴侣：\n{partners = }\n(for嵌套手撕)\n\npartners = {[i for i in combinations(nums, 2) if isPrime(sum(i))]}\n(调用combinations())")# 从输入数组中中删除已取组合数字
def myremove(partner: tuple) -> None:a, b = partnerif a in c and b in c:c.remove(a)c.remove(b)return 1 # 成功取数返回1return 0 # 取数不成功返回0# 找最佳组合
result: int = 0 # 最后输出的最大组数
for i in partners: # m外层循环是从输入数组中取第一个组合k: int = 0 # 当前取法计数器c = nums[:] # 输入数组副本k += myremove(i) # 计数d = partners[:] # 所有合规组合副本d.remove(i) # 删除外层循环的那一组for j in d: # 遍历其余合规组合k += myremove(j) # 在输入数组中查找并计数result = max(result, k) # 记录最大数量的素数伴侣组合数print(f"\n输出：{result}")


    回页首

    上一篇：  素数判定算法优化(常规写法亲民，高效写法炼人。用素数的基本特性写，易读易懂；用6k±1特性写，高效但却得有学过《数论》)
    下一篇： 


    我的HOT博：

      本次共计收集 311 篇博文笔记信息，总阅读量43.82w。数据于2024年03月22日 00:50:22完成采集，用时6分2.71秒。阅读量不小于6.00k的有 7 7 7篇。

    • 001
      标题：让QQ群昵称色变的神奇代码
      (浏览阅读 5.9w )
      地址：https://blog.csdn.net/m0_57158496/article/details/122566500
      点赞：25 收藏：86 评论：17
      摘要：让QQ昵称色变的神奇代码。
      首发：2022-01-18 19:15:08
      最后编辑：2022-01-20 07:56:47

    • 002
      标题：Python列表(list)反序(降序)的7种实现方式
      (浏览阅读 1.1w )
      地址：https://blog.csdn.net/m0_57158496/article/details/128271700
      点赞：8 收藏：35 评论：8
      摘要：Python列表(list)反序(降序)的实现方式：原址反序，list.reverse()、list.sort()；遍历，全数组遍历、1/2数组遍历；新生成列表，resersed()、sorted()、负步长切片[::-1]。
      首发：2022-12-11 23:54:15
      最后编辑：2023-03-20 18:13:55

    • 003
      标题：pandas 数据类型之 DataFrame
      (浏览阅读 9.7k )
      地址：https://blog.csdn.net/m0_57158496/article/details/124525814
      点赞：7 收藏：36 
      摘要：pandas 数据类型之 DataFrame_panda dataframe。
      首发：2022-05-01 13:20:17
      最后编辑：2022-05-08 08:46:13

    • 004
      标题：个人信息提取(字符串)
      (浏览阅读 8.2k )
      地址：https://blog.csdn.net/m0_57158496/article/details/124244618
      点赞：2 收藏：15 
      摘要：个人信息提取(字符串)_个人信息提取python。
      首发：2022-04-18 11:07:12
      最后编辑：2022-04-20 13:17:54

    • 005
      标题：Python字符串居中显示
      (浏览阅读 7.6k )
      地址：https://blog.csdn.net/m0_57158496/article/details/122163023
      评论：1

    • 006
      标题：罗马数字转换器|罗马数字生成器
      (浏览阅读 7.5k )
      地址：https://blog.csdn.net/m0_57158496/article/details/122592047
      摘要：罗马数字转换器|生成器。
      首发：2022-01-19 23:26:42
      最后编辑：2022-01-21 18:37:46

    • 007
      标题：回车符、换行符和回车换行符
      (浏览阅读 6.0k )
      地址：https://blog.csdn.net/m0_57158496/article/details/123109488
      点赞：2 收藏：3 
      摘要：回车符、换行符和回车换行符_命令行回车符。
      首发：2022-02-24 13:10:02
      最后编辑：2022-02-25 20:07:40

    推荐条件 阅读量突破6.00k
    (更多热博，请点击蓝色文字跳转翻阅)
    • 截屏图片
      在这里插入图片描述
        (此文涉及ChatPT，曾被csdn多次下架，前几日又因新发笔记被误杀而落马。躺“未过审”还不如回收站，回收站还不如永久不见。😪值此年底清扫，果断移除。留此截图，以识“曾经”。2023-12-31)


    回页首

    老齐漫画头像

    精品文章：

    • 好文力荐：齐伟书稿 《python 完全自学教程》 Free连载(已完稿并集结成书，还有PDF版本百度网盘永久分享，点击跳转免费🆓下载。)
    • OPP三大特性：封装中的property
    • 通过内置对象理解python'
    • 正则表达式
    • python中“*”的作用
    • Python 完全自学手册
    • 海象运算符
    • Python中的 `!=`与`is not`不同
    • 学习编程的正确方法

    来源：老齐教室

    ◆ Python 入门指南【Python 3.6.3】

    好文力荐：

    • 全栈领域优质创作者——[寒佬](还是国内某高校学生)博文“非技术文—关于英语和如何正确的提问”，“英语”和“会提问”是编程学习的两大利器。
    • 【8大编程语言的适用领域】先别着急选语言学编程，先看它们能干嘛
    • 靠谱程序员的好习惯
    • 大佬帅地的优质好文“函数功能、结束条件、函数等价式”三大要素让您认清递归

    CSDN实用技巧博文：

    • 8个好用到爆的Python实用技巧
    • python忽略警告
    • Python代码编写规范
    • Python的docstring规范（说明文档的规范写法）

这篇关于最大组数的“素数伴侣”的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/984246。

相关文章

如何提高Redis服务器的最大打开文件数限制

如何提高Redis服务器的最大打开文件数限制

《如何提高Redis服务器的最大打开文件数限制》文章讨论了如何提高Redis服务器的最大打开文件数限制,以支持高并发服务,本文给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录如何提高Redis服务器的最大打开文件数限制问题诊断解决步骤1. 修改系统级别的限制2. 为Redis进程特别设置限制
阅读更多...
poj 3723 kruscal，反边取最大生成树。

poj 3723 kruscal，反边取最大生成树。

题意： 需要征募女兵N人，男兵M人。 每征募一个人需要花费10000美元，但是如果已经招募的人中有一些关系亲密的人，那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度，征募某个人的费用是10000 - （已经征募的人中和自己的亲密度的最大值）。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析： 先设想无向图，在征募某个人a时，如果使用了a和b之间的关系
阅读更多...
poj 3258 二分最小值最大

poj 3258 二分最小值最大

题意： 有一些石头排成一条线，第一个和最后一个不能去掉。 其余的共可以去掉m块，要使去掉后石头间距的最小值最大。 解析： 二分石头，最小值最大。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c
阅读更多...
poj 2175 最小费用最大流TLE

poj 2175 最小费用最大流TLE

题意： 一条街上有n个大楼，坐标为xi，yi，bi个人在里面工作。 然后防空洞的坐标为pj，qj，可以容纳cj个人。 从大楼i中的人到防空洞j去避难所需的时间为 abs（xi - pi） + （yi - qi） + 1。 现在设计了一个避难计划，指定从大楼i到防空洞j避难的人数 eij。 判断如果按照原计划进行，所有人避难所用的时间总和是不是最小的。 若是，输出“OPETIMAL",若
阅读更多...
poj 2135 有流量限制的最小费用最大流

poj 2135 有流量限制的最小费用最大流

题意： 农场里有n块地，其中约翰的家在1号地，二n号地有个很大的仓库。 农场有M条道路（双向），道路i连接着ai号地和bi号地，长度为ci。 约翰希望按照从家里出发，经过若干块地后到达仓库，然后再返回家中的顺序带朋友参观。 如果要求往返不能经过同一条路两次，求参观路线总长度的最小值。 解析： 如果只考虑去或者回的情况，问题只不过是无向图中两点之间的最短路问题。 但是现在要去要回
阅读更多...
poj 2594 二分图最大独立集

poj 2594 二分图最大独立集

题意： 求一张图的最大独立集，这题不同的地方在于，间接相邻的点也可以有一条边，所以用floyd来把间接相邻的边也连起来。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <sta
阅读更多...
poj 3422 有流量限制的最小费用流 反用求最大 + 拆点

poj 3422 有流量限制的最小费用流 反用求最大 + 拆点

题意： 给一个n*n（50 * 50） 的数字迷宫，从左上点开始走，走到右下点。 每次只能往右移一格，或者往下移一格。 每个格子，第一次到达时可以获得格子对应的数字作为奖励，再次到达则没有奖励。 问走k次这个迷宫，最大能获得多少奖励。 解析： 拆点，拿样例来说明： 3 2 1 2 3 0 2 1 1 4 2 3*3的数字迷宫，走两次最大能获得多少奖励。 将每个点拆成两个
阅读更多...
poj 3692 二分图最大独立集

poj 3692 二分图最大独立集

题意： 幼儿园里，有G个女生和B个男生。 他们中间有女生和女生认识，男生男生认识，也有男生和女生认识的。 现在要选出一些人，使得这里面的人都认识，问最多能选多少人。 解析： 反过来建边，将不认识的男生和女生相连，然后求一个二分图的最大独立集就行了。 下图很直观： 点击打开链接 原图： 现图： 、 代码： #pragma comment(
阅读更多...
最大流、 最小费用最大流终极版模板

最大流、 最小费用最大流终极版模板

最大流  const int inf = 1000000000 ;const int maxn = 20000 , maxm = 500000 ;struct Edge{int v , f ,next ;Edge(){}Edge(int _v , int _f , int _next):v(_v) ,f(_f),next(_next){}};int sourse , mee
阅读更多...
二分最大匹配总结

二分最大匹配总结

HDU 2444  黑白染色 ，二分图判定 const int maxn = 208 ;vector<int> g[maxn] ;int n ;bool vis[maxn] ;int match[maxn] ;;int color[maxn] ;int setcolor(int u , int c){color[u] = c ;for(vector<int>::iter
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2