다면체 소수(Dihedral Prime)란 무엇일까?
숫자 n이 주어졌을 때, 이 수가 다면체 소수(dihedral prime)인지 판별하는 문제입니다. 다면체 소수란 그 수 자체가 소수이면서, 7세그먼트 디스플레이(계산기나 디지털 시계에 사용되는 숫자 표시 방식)로 나타냈을 때 디스플레이를 정방향으로 보든 거꾸로 돌려 보든 항상 같은 숫자 또는 다른 소수로 읽히는 수를 의미합니다.
예를 들어 n = 1181을 입력하면 결과는 True입니다.
1181을 7세그먼트 디스플레이에 표시한 뒤 180도 회전해도 여전히 1181로 읽히며, 원래 수와 뒤집힌 수 모두 소수이기 때문입니다.
문제 해결 접근 방법
이 문제는 다음 세 단계로 나누어 해결할 수 있습니다.
1단계: 숫자를 거꾸로 뒤집는 함수 만들기
먼저 up_side_down() 함수를 정의합니다. 이 함수는 입력받은 수를 뒤집은 값을 반환하며, 7세그먼트 디스플레이에서 상하 반전 시 서로 바뀌어 보이는 2와 5를 서로 교체해 줍니다.
- temp = n, total = 0으로 초기화합니다.
- temp가 0보다 큰 동안 다음 과정을 반복합니다.
- d = temp mod 10 으로 마지막 자릿수를 구합니다.
- d가 2이면 5로, d가 5이면 2로 변경합니다.
- total = total × 10 + d 로 자릿수를 누적합니다.
- temp를 10으로 나눈 몫으로 갱신합니다.
- 반복이 끝나면 total을 반환합니다.
2단계: 네 가지 형태가 모두 소수인지 검사하기
메인 로직에서는 아래 네 가지 값이 모두 소수인지 확인합니다.
- 원래 수 n
- 상하 반전한 수 up_side_down(n)
- 역순으로 읽은 수 reverse(n)
- 반전한 수를 다시 역순으로 읽은 reverse(up_side_down(n))
이 중 하나라도 소수가 아니면 False를 반환합니다.
3단계: 유효하지 않은 자릿수 걸러내기
마지막으로 n의 각 자릿수를 검사하여 3, 4, 6, 7, 9가 포함되어 있으면 False를 반환합니다. 이 숫자들은 7세그먼트 디스플레이에서 뒤집었을 때 올바른 숫자로 인식되지 않기 때문입니다.换句话说, 다면체 소수는 오직 0, 1, 2, 5, 8의 자릿수만으로 구성되어야 합니다. 모든 검사를 통과하면 True를 반환합니다.
구현 코드
아래 코드는 에라토스테네스의 체(Sieve of Eratosthenes)를 이용해 미리 소수 테이블을 만들어 둔 뒤, 앞서 설명한 조건들을 순서대로 검사하는 방식입니다.
prime = (int(1e5)+5)*[True]
def reverse(n):
return int(str(n)[::-1])
def up_side_down(n):
temp = n
total = 0
while temp > 0:
d = temp % 10
if d == 2:
d = 5
elif d == 5:
d = 2
total = total * 10 + d
temp //= 10
return total
def get_all_prime():
prime[0] = prime[1] = False
for i in range(2, int(1e5)+1):
j = 2
while i * j <= int(1e5):
prime[i * j] = False
j += 1
def solve(n):
get_all_prime()
if not prime[n] or not prime[up_side_down(n)] or not prime[reverse(n)] or not prime[reverse(up_side_down(n))]:
return False
temp = n
while temp > 0:
rem = temp % 10
if rem in [3, 4, 6, 7, 9]:
return False
temp //= 10
return True
n = 1181
print(solve(n))
실행 결과
n = 1181을 대입해 실행하면 다음과 같은 결과를 얻습니다.
True
마무리
이 알고리즘은 에라토스테네스의 체로 소수를 빠르게 미리 계산해 두고, 자릿수 유효성 검사와 네 방향의 소수 검사를 결합해 다면체 소수 여부를 정확하게 판별합니다. 참고로 실제 다면체 소수에는 2, 5, 11, 101, 181, 1181, 1811, 18181 등이 있으며, 이 수들은 어떤 방향에서 읽어도 소수라는 독특한 성질을 지니고 있습니다.