题解 | #素数伴侣#

写了1天.....

解答步骤写的比较详细

def getPrimes(n):
    """获取2~n之间的素数，用于对素数进行判断"""
    primes = [True for _ in range(n+1)]
    for i in range(2, n+1):
        if primes[i]:
            yield i
            for j in range(i+i, n+1, i):
                primes[j] = False

def splitNums(nums):
    """用于将数字分为奇数和偶数部分"""
    odd = []
    even = []
    oddLen = 0
    evenLen = 0
    for num in nums:
        if num % 2 == 0:
            even.append(num)
            evenLen += 1
        else:
            odd.append(num)
            oddLen += 1
    return odd, oddLen, even, evenLen 

def removeValue(data, n, i, k):
    """从data的第i行开始去掉数字i"""
    for j in range(i, n):
        if k in data[j]:
            data[j].remove(k)
    return data 

def countValue(data, n, i, d):
    """统计data从i行开始，d中的元素总共出现的次数"""
    d = {k: 0 for k in d}
    for j in range(i, n):
        for value in data[j]:
            if value in d:
                d[value] += 1
    return d 

def func(nums):
    odd, oddLen, even, evenLen = splitNums(nums)
    maxGroup = min(oddLen, evenLen)
    if maxGroup == 0:   # 如果没有奇数或者偶数，那么直接必定不会出现素数伴侣
        return 0 
    primes = list(getPrimes(max(odd)+max(even)))
    # 每一行代表1个偶数，每一列代表一个奇数
    # 此处得到每个一行的偶数能和哪几个奇数组成素数伴侣
    data = [[j for j in range(oddLen) if even[i] + odd[j] in primes] for i in range(evenLen)]
    data = [row for row in data if row]  # 去掉不能和任何数字组成伴侣的偶数行
    if not data:  # 为空表示没有任何偶数能和奇数组成伴侣
        return 0 
    stack = []  # 存储结果用容器
    n = len(data)   
    for i in range(n-1):  
        # 分别对每一行进行迭代，判断改行是否符合一下的某一种情况（最后1行不需要判断，直接取最后1行的第一个数据即可）
        # 1 如果这一行为空，那么直接忽略这一行
        # 2 这一行只能和1个奇数 K 组成伴侣，那么就取这个偶数和K组成伴侣
        # 3 若这一行可以和多个奇数组成伴侣，那么去查找K，要求：后面行重复使用到K的次数最少
        # 4 去掉后面行用到的K
        # 5 若出现情况如：[[1,2], [1], [2, 3], [2, 4]]，避免第一行取到1，
        #    在每一次取数之前，将数据按照候选奇数的多少依次排列
        data = data[:i] + sorted(data[i:], key=lambda x: len(x))
        if len(data[i]) == 0:
            continue
        if len(data[i]) == 1:
            stack.append(data[i][0])
            data = removeValue(data, n, i+1, data[i][0])
            continue
        d = countValue(data, n, i+1, data[i])
        minValue = data[i][0]
        c = d[minValue]
        if c == 0:
            stack.append(data[i][0])
            data = removeValue(data, n, i+1, data[i][0])
            continue
        for k, v in d.items():
            if v < k:
                minValue = k
                c = v
        stack.append(minValue)
        if c == 0:
            continue
        data = removeValue(data, n, i+1, minValue)
    if data[-1]:  # 最后1行不需要判断，直接取最后1行的第一个数据即可 
        stack.append(data[-1][0])
    return len(stack)


while True:
    try:
        n = int(input())
        nums = list(map(int, input().strip().split()))
        print(func(nums))
    except EOFError: break