python:素数伴侣

81 阅读 0 评论 54 点赞

我是靠谱客的博主懦弱冰淇淋，这篇文章主要介绍python:素数伴侣，现在分享给大家，希望可以做个参考。

题目描述

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

输入:

有一个正偶数N（N≤100），表示待挑选的自然数的个数。后面给出具体的数字，范围为[2,30000]。

输出:

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

输入描述:

输入说明
1 输入一个正偶数n
2 输入n个整数
注意：数据可能有多组

输出描述:

求得的“最佳方案”组成“素数伴侣”的对数。

示例1

输入

复制代码

输出

复制代码

实现

复制代码

# 判断是否为素数
def is_prime(number):
    for i in range(2, number):
        if number % i == 0:
            return False
    return True

# 素数一定为奇数，将number分成奇偶两个列表
def odd_even():
    odd = []
    even = []
    for i in numbers:
        if i % 2 == 1:
            odd.append(int(i))
        else:
            even.append(int(i))
    return odd, even

# 判断是否可以配对,记录为字典{odd(index:[even[index]])}
def group_prime():
    primes = {}
    for i in range(len(odd)):
        primes[i] = []

for index_i, i in enumerate(odd):
        for index_j, j in enumerate(even):
            if is_prime(i + j):
                primes[index_i].append(index_j)
            else:
                primes[index_i].append(-1)
    return primes

# 匹配最佳配对方案
def mate(odd_key):
    for index, i in enumerate(even):
        if primes[odd_key][index] != -1 and used[index] == 0:
            used[index] = 1
            if companion[index] == -1 or mate(companion[index]) != 0:  # 已配对的伴侣是可以重新选择伴侣
                companion[index] = odd_key
                return 1
    return 0

while 1:
    try:
        n = int(input())
        numbers = list(map(int, input().strip().split()))
        odd, even = odd_even()
        primes = group_prime()
        new = []
        companion= [-1 for i in range(len(even))]  # 已配对的素数伴侣
        count = 0
        for k, v in primes.items():
            used = [0 for i in range(len(even))]  # 是否已被配对
            if mate(k):
                count += 1
        print(count)
    except:
        break

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
# 判断是否为素数
def is_prime(number):
    for i in range(2, number):
        if number % i == 0:
            return False
    return True


# 素数一定为奇数，将number分成奇偶两个列表
def odd_even():
    odd = []
    even = []
    for i in numbers:
        if i % 2 == 1:
            odd.append(int(i))
        else:
            even.append(int(i))
    return odd, even


# 判断是否可以配对,记录为字典{odd(index:[even[index]])}
def group_prime():
    primes = {}
    for i in range(len(odd)):
        primes[i] = []

    for index_i, i in enumerate(odd):
        for index_j, j in enumerate(even):
            if is_prime(i + j):
                primes[index_i].append(index_j)
            else:
                primes[index_i].append(-1)
    return primes


# 匹配最佳配对方案
def mate(odd_key):
    for index, i in enumerate(even):
        if primes[odd_key][index] != -1 and used[index] == 0:
            used[index] = 1
            if companion[index] == -1 or mate(companion[index]) != 0:  # 已配对的伴侣是可以重新选择伴侣
                companion[index] = odd_key
                return 1
    return 0


while 1:
    try:
        n = int(input())
        numbers = list(map(int, input().strip().split()))
        odd, even = odd_even()
        primes = group_prime()
        new = []
        companion= [-1 for i in range(len(even))]  # 已配对的素数伴侣
        count = 0
        for k, v in primes.items():
            used = [0 for i in range(len(even))]  # 是否已被配对
            if mate(k):
                count += 1
        print(count)
    except:
        break