【Python】数値のすべての回転が素数かどうかを判定するプログラム

ある整数 n が与えられたとき、その桁を入れ替えてできるすべての回転数が素数であるかどうかを判定します。このような性質を持つ数は「循環素数（circular prime）」として知られています。

例えば、入力が n = 13 の場合を考えてみましょう。13 自体が素数であり、桁を入れ替えた 31 も素数であるため、出力は True になります。

解決のアプローチ

この問題は、以下の手順で解くことができます。

1. 数値 n を文字列に変換します。
2. n の桁数と同じ回数だけループ処理を行います。
   • 現在の n が素数でなければ、False を返します。
   • 素数であれば、先頭の桁を取り出して末尾に移動し、新しい n を作ります。
3. すべての回転が素数であれば、最後に True を返します。

実装例

それでは、実際のPythonコードを見てみましょう。

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

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

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

入力

13

出力

True

コードの解説

素数判定関数（is_prime）

内部関数 is_prime は、試し割り法によって素数判定を行います。まず 1 以下の数は素数ではないため False を返し、その後、2 および 3 以上の奇数（√num まで）で割り切れるかどうかを確認します。割り切れる数が存在しなければ素数と判断できます。

回転の生成方法

回転は文字列スライスによって簡単に実現できます。n[1:] + n[0] により、先頭の1文字を取り除いた残りに先頭の文字を連結することで、桁を左に回転させた新しい数を作れます。これを桁数分繰り返すことで、すべての回転パターンを網羅的にチェックできます。

なお、回転の過程で先頭に 0 が現れた場合（例：103 → 031）でも、int() による変換で自動的に 31 として扱われるため、特別な処理は不要です。

計算量

桁数を d、元の数値を n とすると、各回転ごとの素数判定は O(√n)、回転は全部で d 回行うため、全体の計算量は O(d・√n) となります。桁数が少ない範囲では非常に効率的に動作します。