题解 | #素数伴侣#给个不一样的解法：建图+贪心

将可以组成 素数伴侣 的一对数字 看成 相连的两个节点，建一个无向图，并统计每个节点的度

每次从节点中选择 度 最小 的节点，再选择与它相连的 度 最小的节点。之后将他们从图中删除。

import math

n = int(input())
nums = list(map(int, input().split()))

def isPrime(x):
    if x == 2:
        return True
    for d in range(2, int(math.sqrt(x))+1):
        if x%d == 0:
            return False
    return True

# 能组成一对素数伴侣的下标，建立成无向图
G = [set() for _ in range(n)]
for i in range(len(nums)):
    for j in range(i+1, len(nums)):
        if isPrime(nums[i]+nums[j]):
            G[i].add(j)
            G[j].add(i)

# 统计节点的度
degrees = [len(G[i]) for i in range(n)]
res = 0
def deleteNode(x):
    # 从图中删除节点
    degrees[x] = 0
    for y in G[x]:
        G[y].discard(x)
        degrees[y] -= 1
    G[x].clear()

while True:

    # 找到度最小的节点
    minn = 1000000000
    x = -1
    for i in range(n):
        if degrees[i] > 0:
            if degrees[i] < minn:
                minn = degrees[i]
                x = i
    if x == -1:
        break
    minn = 1000000000
    y = -1
    
    # 从找到节点的邻接节点中再找一个度最小的节点
    for i in G[x]:
        if degrees[i] > 0:
            if degrees[i] < minn:
                minn = degrees[i]
                y = i
    if y == -1:
        break
    # 删除这两个节点
    deleteNode(x)
    deleteNode(y)
    res += 1
print(res)