파이썬으로 숫자의 모든 회전이 소수인지 확인하는 프로그램

숫자 n이 주어졌을 때, n의 자릿수를 순환시켜 얻을 수 있는 모든 회전(rotations)이 소수인지 아닌지 확인해야 합니다.

예를 들어 입력이 n = 13이라면 출력은 True가 됩니다. 13 자체가 소수이고, 자릿수를 회전한 31 역시 소수이기 때문입니다. 이처럼 모든 회전이 소수가 되는 수는 '회전 소수(circular prime)'라고도 불립니다.

접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

• 숫자 n을 문자열로 변환합니다.
• n의 길이만큼 반복하면서 다음을 수행합니다.
  • 현재 숫자가 소수가 아니라면 False를 반환합니다.
  • 그렇지 않다면 문자열의 첫 번째 자릿수를 맨 뒤로 이동시켜 다음 회전을 만듭니다.
• 모든 회전이 소수라면 True를 반환합니다.

예제 코드

아래 구현을 통해 더 잘 이해할 수 있습니다.

class Solution:
    def solve(self, n):
        def is_prime(num):
            if num <= 1:
                return False
            if num % 2 == 0:
                return num == 2
            for i in range(3, int(num ** 0.5) + 1, 2):
                if num % i == 0:
                    return False
            return True

        s = str(n)
        for _ in range(len(s)):
            if not is_prime(int(s)):
                return False
            s = s[1:] + s[0]
        return True

ob = Solution()
print(ob.solve(13))

입력

13

출력

True

동작 과정 설명

입력값 13에 대해 코드가 동작하는 과정은 다음과 같습니다.

1. "13"을 정수로 변환한 값 13은 소수이므로 통과합니다.
2. 첫 자릿수를 뒤로 보내 "31"을 만듭니다.
3. 31 역시 소수이므로 통과합니다.
4. 모든 회전을 검사했으므로 최종적으로 True를 반환합니다.

복잡도 분석

숫자의 자릿수를 d라고 할 때, 총 d번의 회전마다 소수 판별을 수행합니다. 소수 판별은 제곱근까지만 검사하므로 O(√n)의 시간이 걸리고, 전체 시간 복잡도는 대략 O(d × √n)입니다. 자릿수가 많지 않은 일반적인 입력에서는 매우 효율적으로 동작합니다.