【Project Euler】Problem 35: 循環素数

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 35：循環素数

原文 Problem 35: Circular primes

問題の要約：$p<10^6$の素数で桁を循環させたすべての数も素数になるものの合計を求めよ

まずはそのまま$p<10^6$のすべての素数で循環素数のチェックをして数えます。

from sympy import nextprime, isprime

def isCircularPrime(pstr):
  for i in range(len(pstr)-1):
    pstr = pstr[1:]+pstr[0]   # rotate one digit
    if not isprime(int(pstr)):
      return False
  return True

N = 10**6
nCirPrime, p = 0, 1
while p < N:
  p = nextprime(p)
  pstr = str(p)
  if isCircularPrime(pstr): 
    nCirPrime += 1
print(f"Answer is {nCirPrime}")

今回の答えはこれでいいのですが、これは循環したものを重複して数えています。Circular prime(Wikipedia)によれば（日本語はないのが寂しいですが、、、）$p<10^6$の循環素数は19個しかないとのことなので重複を除いたすべての循環素数を出力するプログラムも作りました。

from sympy import nextprime, isprime

def CirPrimeList(pstr):
  ret = set({int(pstr)})
  for i in range(len(pstr)-1):
    pstr = pstr[1:]+pstr[0]   # rotate one digit
    if not isprime(int(pstr)):
      return set()
    ret.add(int(pstr))
  return ret

N = 10**6
cpset = set()
CirPrime, p = [], 1
while p < N:
  p = nextprime(p)
  if p in cpset: continue
  pstr = str(p)
  cps = CirPrimeList(pstr)
  if len(cps )>0:
    CirPrime += [p]
    cpset |= cps

print(f"Answer {len(CirPrime)}, {CirPrime}")
#Answer 19, [2, 3, 5, 7, 11, 13, 17, 37, 79, 113, 197, 199, 337, 1193, 3779, 11939, 19937, 193939, 199933]

（開発環境：Google Colab）