素数伴侣最大组合数

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

(笔记模板由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$ 】
本文地址： https://blog.csdn.net/m0_57158496/article/details/138726901

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 \leq n \leq 100$ ，输入的数据大小满足 $2 < v a l \leq 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$ 。🙏🙏🙏

代码运行效果截屏图片

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

接下来，实施解题：

1、要确定“素数伴侣”，得有素数判定的代码。简单！ $n e w$ 一个。

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 = partner
    if a in c and b in c:
        c.remove(a)
        c.remove(b)
        return 1 # 成功取数返回1

    return 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、我关于素数的学习笔记

回页目录

4、完整源码(Python)

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

#!/sur/bin/nve python 
# coding: utf-8 
from itertools import combinations


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 # 经过前面的排查，就只剩素数了


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 = partner
    if a in c and b in c:
        c.remove(a)
        c.remove(b)
        return 1 # 成功取数返回1

    return 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$ 篇。

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