[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인 집합 가운데 모든 원소가 새로 찾은 원소가 연결되는지 확인하면 된다.

?

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

<code>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]))</code>

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