네 개의 소수 3, 7, 109, 673은 상당히 특이한 성질이 있습니다. 넷 중에 아무것이나 두 개를 골라서 어떤 쪽으로 이어붙이던지 그 결과도 소수가 됩니다. 예를 들어 7과 109를 고르면 1097, 7109 모두 소수입니다. 2, 7, 109, 673은 이런 성질을 가진 네 소수 중에서 그 합이 792로 가장 작습니다. 다섯 소수 중에 어떤 두 개를 골라 이어붙여도 소수가 되는 수들을 찾아서 그 합의 최소값을 구하세요.
접근
두 소수를 방향에 상관없이 이어붙였을 때에도 모두 소수가 되는 소수 5개의 조합을 찾는 문제이다. 단순히 접근하려해도 언뜻 생각하면 굉장히 복잡한 문제처럼 보여서 쉽지 않을 것 같다. 가장 큰 문제는 어느 범위 내에서 이 조건을 만족하는 소수들을 찾을 수 있을까 하는 점이다. 문제에서 제시한 예는 조건을 만족하는 4개의 소수 집합을 찾는데, 모든 원소가 3자리 이내의 소수라는 점을 알 수 있다. 따라서 3자리, 4자리, 5자리 등으로 범위를 점점 확대해가면서 찾으면 될 것이다.
소수 이어붙이기
숫자 이어붙이기는 앞선 문제들에서도 몇 번 소개된 적이 있는 방법이니 긴 설명은 하지 않겠다. 여기서 이어 붙이는 대상들은 2를 제외한 소수이다. 따라서 끝자리 체크등은 따로 수행할 필요가 없지만, 3의 배수여부는 미리 알아낼 수 있다. 3을 제외한 모든 소수들은 3으로 나눈 나머지가 1 아니면 2이다. 만약 3으로 나눈 나머지가 1인 소수와 2인 소수를 이어붙이면 이 수는 3의 배수가 되기에, 3을 제외하면 3으로 나눈 나머지가 같은 소수들만 비교해도 된다.
(* 이 풀이에서 사용된 소수검사함수, 소수체 생성, 메모이제이션 함수는 코드를 생략한다.)
from math import log10
@memoize
def check(a: int, b: int) -> bool:
if a != 3 and a % 3 != b % 3:
return False
x = a * 10**(int(log10(b) + 1) + b
y = b * 10**(int(log10(a) + 1) + a
return isprime(x) and isprime(y)풀이
사실 이 문제의 풀이는 ‘조합’의 모든 경우를 구하는 것과 동일하다. 임의로 지정한 범위 내의 모든 소수의 조합을 대상으로 해도 되지만, 사용할 수 없는 소수조합을 포함하는 경우가 훨씬 많을 것이기 때문에, 직접 구현하는 쪽이 성능이 더 좋을 것이다.
def helper(head, tail, k):
if k == 0:
yield head
return
for i, p in enumerate(tail):
if all(check(x, p) for x in head):
yield from helper(
(*head, p),
[x for x in tail[i+1:] if check(p, x)],
k - 1
)각 소수를 조건에 맞는지 수집한 후에는 그 수보다 큰 남아있는 소수 중에서 방금 추가한 소수와 이어붙여서 소수를 만들 수 있는 수로만 후보를 제한하면, 반복횟수를 그마나 조금 더 줄일 수 있는데, 한 번의 처리에 대한 오버헤드는 커지지만, 전체적으로는 반복횟수를 많이 줄이기 때문에 성능 향상 효과가 제법 크다.
검증
먼저 1000 이하의 소수 4개를 찾아보자. 앞에서 부터 가장 작은 소수를 먼저 취한다 하더라도 4개의 합이 최소가 되리라는 보장은 없기 때문에, 전수 검사를 해야 한다.
@elapsed
def main():
ps = sieve(1000)[1:]
for xs in helper((), ps, 4):
print(f"{sum(xs)} -> {xs}")
if __name__ == "__main__":
main()
# 792 -> (3, 7, 109, 673)
# 1838 -> (23, 311, 677, 827)
# elapsed: 31.000 ms
문제에서 제시한 [3, 7, 109, 673] 외에도 [23, 311, 677, 827]을 추가로 찾을 수 있다. 그리고 그 중에서 합이 가장 작은 것은 첫번째 조합이다.
3자리 소수에서 5개가 이 조건을 만족하는 경우는 찾을 수 없다. 4자리에서 5개 조건으로 찾아본다면,…. 대략 10초 내외에 1개의 답을 구할 수 있을 것이다. 소수의 개수가 더 많아졌고, 조합의 수는 그만큼 더 많이 늘어나기 때문에 전수 검사에는 제법 시간이 오래 걸린다. 만약 10,000 미만의 소수 중에서 이러한 조합이 단 하나만 존재한다는 사실을 알고 있다면 첫번째 조합을 구한 즉시 루프를 멈추면 된다. (우리는 helper() 함수를 제너레이터 함수로 구현했고, 제너레이터는 lazy하게 작동하기 때문에, 첫번째 조합만 찾고 멈춘다면 매우 빠르게 다을 낼 수 있다.)