정수 N이 주어졌을 때, N 미만에 존재하는 모든 절단 가능 소수(Truncatable Prime)의 합을 구하는 문제를 살펴보겠습니다. 절단 가능 소수는 자릿수를 한쪽 방향에서부터 차례대로 제거해도 남은 수가 계속해서 소수로 유지되는 특별한 성질을 가진 소수입니다.
절단 가능 소수의 정의
- 왼쪽 절단 가능 소수(Left-truncatable prime): 맨 앞자리 숫자부터 한 자리씩 제거했을 때, 생성되는 모든 수가 소수인 경우
- 오른쪽 절단 가능 소수(Right-truncatable prime): 맨 뒷자리 숫자부터 한 자리씩 제거했을 때, 생성되는 모든 수가 소수인 경우
예를 들어 9137은 왼쪽부터 자릿수를 제거하면 137 → 37 → 7이 되는데, 이 값들이 모두 소수이므로 왼쪽 절단 가능 소수에 해당합니다.
문제 예시
입력이 N = 55라면, 55 미만의 절단 가능 소수는 2, 3, 5, 7, 23, 37, 53이며 이들의 합인 130이 출력됩니다.
(2 + 3 + 5 + 7 + 23 + 37 + 53) = 130
풀이 접근 방법
- N := 1000005로 설정하고, 크기 N의 리스트 prime을 True로 초기화합니다.
- sieve() 함수를 정의해 에라토스테네스의 체로 소수 테이블을 만듭니다. prime[0]과 prime[1]은 False로 설정하고, 2부터 N까지 반복하면서 각 소수의 배수를 모두 False로 표시합니다.
- 메인 로직에서는 합계를 0으로 초기화한 뒤, 2부터 n까지의 각 수를 대상으로 검사를 진행합니다.
- 각 수 i에 대해 먼저
current //= 10으로 맨 뒷자리를 하나씩 제거하며, 잘려 나온 모든 수가 소수인지 확인합니다. - 다음으로 power를 10씩 곱해가며
current % power로 맨 앞자리를 하나씩 제거하는 경우도 검사합니다. - 양방향 검사를 모두 통과하면(f가 True) 해당 수를 합계에 더합니다.
- 모든 검사가 끝나면 최종 합계를 반환합니다.
구현 예제
아래 코드를 통해 동작 과정을 더 쉽게 이해할 수 있습니다.
N = 1000005
prime = [True for i in range(N)]
def sieve():
prime[1] = False
prime[0] = False
for i in range(2, N):
if (prime[i] == True):
for j in range(i * 2, N, i):
prime[j] = False
def get_total_of_trunc_primes(n):
total = 0
for i in range(2, n):
current = i
f = True
# 맨 뒷자리부터 제거하며 검사
while (current):
if (prime[current] == False):
f = False
break
current //= 10
current = i
power = 10
# 맨 앞자리부터 제거하며 검사
while (current // power):
if (prime[current % power] == False):
f = False
break
power *= 10
if f:
total += i
return total
n = 55
sieve()
print(get_total_of_trunc_primes(n))입력
55
출력
130
복잡도 분석
에라토스테네스의 체 생성에는 O(N log log N)의 시간이 소요되며, 이후 각 수에 대한 절단 검사는 자릿수 길이에 비례하므로 전체적으로 매우 효율적으로 동작합니다. 참고로 내장 함수 sum과 이름이 충돌하지 않도록 변수명을 total로 사용하는 것이 좋은 코딩 습관입니다.