题解 | #素数伴侣#

素数伴侣

https://www.nowcoder.com/practice/b9eae162e02f4f928eac37d7699b352e

import math

def check_prime(num):
    for i in range(2, int(math.sqrt(num)+1)):
        if num%i == 0:
            return False
    return True

def find_even(odd, evens, choose, visited):
    for j, even in enumerate(evens):
        if check_prime(odd + even) and not visited[j]:
            visited[j] = True
            # 假设第j个 位置的evens还没有被choose;
            # 或者被choose了,但是之前choose它的odd可以选择一个新的even。
            # 那么当前odd可以选择第j个even。
            if choose[j]==0 or find_even(choose[j], evens, choose, visited):
                choose[j] = odd
                return True
    return False

N = int(input().strip())
all_nums = list(map(int, input().strip().split()))
odds = []  # 奇数集合
evens = []  # 偶数集合
for num in all_nums:
    if num%2 == 0:
        evens.append(num)
    else:
        odds.append(num)

count = 0
choose = [0]*len(evens)
for odd in odds:
    visited = [False]*len(evens)
    if find_even(odd, evens, choose, visited):
        count += 1

print(count)


全部评论

相关推荐

重生我想学测开:嵌入式的问题,我准备入行京东外卖了
点赞 评论 收藏
分享
每晚夜里独自颤抖:要求太多的没必要理
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务