[PROJECT_EULER] 60. Prime pair sets

   문제는 이곳에서 확인할 수 있다. 어떤 소수 두개를 앞뒤로 합치면 그 수도 소수가 되는 경우가 있다. 예를 들면, 3과 7, 3과 11 등이 있다. 이를 연결되었다고 하자. 3, 7, 109 그리고 673은 두개의 원소를 뽑았을때 모두 연결되며, 원소의 개수가 4개인 집합 중 합이 가장 작다. 개수가 5인 집합 중 합이 가장 작은 것을 찾고 그 합을 구하는 것이 문제이다.

   3부터 시작하여 소수 판별을 한 뒤, 새로 찾은 소수가 기존의 소수와 연결되는지 판단한다. 길이가 3인 집합이 만들기 위해서는, 연결되는 두 소수를 고른 뒤 모든 원소가 새로 찾은 소수와 연결되는 지 확인하면 된다.

   예를 들어 새로 찾은 소수가 109라고 하자. 기존의 소수로 만들 수 있는 109와 연결된 소수는 {3, 109}, {7, 109}가 있다. 이제 길이가 2인 집합에서 모든 원소가 109와 연결되는지 확인한다. {3, 7}, {3, 37}, ... , {101, 107}에서 모든 원소가 109와 연결되는 집합은 {3, 7} 뿐이다. 이렇게 길이가 3인 집합 {3, 7, 109}를 만든다. 즉, 길이가 k인 집합을 만들기 위해서는 길이가 k-1인 집합 가운데 모든 원소가 새로 찾은 원소가 연결되는지 확인하면 된다.

import sympy  # 소수 판별 함수를 별도로 구현하지 않음 

def is_connected(num1, num2):
    
    for x1, x2 in ((num1, num2), (num2, num1)):
        x = str(x1) + str(x2)
        x = int(x)

        if not sympy.isprime(x):
            return False
    
    return True

prime_cand = 1
prime_list = []
target_pair_set_len = 5

connected = {k: [] for k in range(2, target_pair_set_len + 1)}

while True:
    prime_cand += 2 
    
    if str(prime_cand)[-1] == '5':
        continue 
        
    if not is_prime(prime_cand):
        continue
    
    con2_found = []
    
    for p in prime_list:
        if is_connected(p, prime_cand):
            connected[2].append((p, prime_cand))
            con2_found.append((p, prime_cand))  # 이 부분이 거슬리지만 속도를 위해 추가하였다. 
            
    for coef in range(2, target_pair_set_len):
        
        for pair_set_found in connected[coef]:
            satisfied = 0

            for p in pair_set_found:
                if not (p, prime_cand) in con2_found:
                    break
                else:
                    satisfied += 1

            if satisfied == coef:
                upper_pair_set = list(pair_set_found) + [prime_cand]
                upper_pair_set = tuple(upper_pair_set)
                connected[coef+1].append(upper_pair_set)
            
    prime_list.append(prime_cand)
    
    if len(connected[target_pair_set_len]) == 1:
        break

ans_pair_set = connected[target_pair_set_len]

print(ans_pair_set[0])
print(sum(ans_pair_set[0]))

   길이가 5인 집합 중 합이 가장 작은 것은 {13, 5197, 5701, 6733, 8389}이며, 답은 26033이다.