프로젝트 오일러 037
문제
사이냅소프트
한자리씩 없애기
이 문제는 원래의 수의 숫자에 특정한 조작을 가해도 여전히 소수가 되는 수를 찾는 다는 점에서 35번 원형소수 문제와 유사한 점이 있지만, 실제로는 상당히 다른 문제입니다. 무엇보다 11개라는 개수는 주어지지만, 범위가 주어지지 않습니다. 따라서 에라토스테네스의 체를 사용하기는 어렵고, 소수 판별 함수를 사용해서 판별해야 하고, 따라서 범위를 좁히는 것에 상당한 노력을 기울여야 합니다.
원형 소수 문제에서 끝자리가 짝수이거나 5여서는 안된다는 조건은 이미 언급한 바 있습니다. 그래서 이 문제에서도 1, 3, 7, 9로 만 이루어진 수들이라고 단정하기 쉬운데, 2와 5는 한자리 수에서는 소수이므로, 맨 앞 숫자로서는 올 수 있습니다. 즉 이 기준을 만족할 수 있는 수는 다음의 조건을 만족해야 합니다.
- 첫번째 숫자로는 1, 2, 3, 5, 7, 9가 올 수 있습니다.
- 나머지 자리 숫자로는 1, 3, 7, 9만 올 수 있습니다.
그 다음은 숫자를 왼쪽이나 오른쪽에서 지워나가는 것입니다. 문제에서 예로든 3797에서 파생되는 숫자들의 순서를 조금 조절해 보면 다음과 같이 앞 부분을 지운 조각과 뒷 부분을 지운 조각들이 서로 짝이 맞는 것들이 있음을 쉽게 알아 볼 수 있습니다.
3797, (3, 797), (37, 97), (379, 7)
숫자의 판단이나 분리를 위해서는 정수를 문자열로 바꾸고 조각들을 모은 후, 명백히 소수가 아닌 것이 포함되는 것을 제외한 후 정수로 변환하여 검사하겠습니다.
참고로 하나의 정수는 다른 수의 일부분이 될 수 있어, 소수 판별 검사 결과는 메모이제이션을 통해 캐싱하는 것이 유리합니다.
cache = {}
def isprime(n):
if n in cache:
return cache[n]
if n < 2:
return False
if n < 4:
return True
if n % 2 == 0 or n % 3 == 0:
return False
if n < 10:
return True
k, l = 5, int(n ** 0.5 + 1.5)
while k < l:
if n % k == 0 or n % (k + 2) == 0:
return False
k += 6
cache[n] = True
return True
def make_splits(n: int) -> list[int]:
x1 = set('123579')
x2 = set('1379')
s = f'{n}'
if not (s[0] in x1 and set(s[1:]) < x2):
return []
res = sum([[s[:i], s[i:]] for i in range(1, len(s))], [])
return list(map(int, (*res, s)))
def main():
res = 0
cnt = 0
n = 11
while cnt < 11:
ns = make_splits(n)
if ns:
if all(map(isprime, ns)):
res, cnt = res + n, cnt + 1
n += 2
return res
print(main())여기서는 정수를 문자열로 바꾸어처리하는 방법을 사용했는데, 2, 3을 제외하고 11부터 모든 홀수를 체크해도 괜찮습니다. 정수의 경우 10의 거듭제곱으로 나눈 몫과 나머지로 분리할 수 있기 때문입니다 (게다가 divmod()는 상당히 빠릅니다.)
