Project Euler 35「巡回素数」

素数判定がちょいちょい出てくるので少しお勉強してちゃんとした関数にしておいた。

Problem 35 「巡回素数」

197は巡回素数と呼ばれる. 桁を回転させたときに得られる数 197, 971, 719 が全て素数だからである.
100未満には巡回素数が13個ある: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, および97である.
100万未満の巡回素数はいくつあるか?

def hoge(num):
    cnt = 1 # 2をカウントしておく
    for n in range(3, num, 2): # 2以外の素数は奇数
        lst_n = list(str(n))
        flg = True
        for i in range(len(lst_n)):
            if not is_prime(int(''.join(lst_n))):
                flg = False
                break
            lst_n.append(lst_n.pop(0)) # 先頭の数字を最後尾に
        if flg == True: cnt += 1
    return cnt

import math
def is_prime(n): # 素数判定
    if n < 2: return False
    elif n == 2: return True
    elif n % 2 == 0: return False
    for i in range(3, int(math.sqrt(n))+1, 2):
        if n % i == 0: return False
    return True

print(hoge(1000000))

でも結構時間かかるなあ。

追記

2桁以上で「0,2,4,5,6,8」を含む場合を無視するようにするとある程度高速化できそう。
賢いなあ。
https://qiita.com/cof/items/7dfc4e8f5ab1b4727cd0

def hoge(num):
    ignore_digits = set('024568')
    cnt = 1
    for n in range(3, num, 2):
        lst_n = list(str(n))
        if len(lst_n) > 1 and ignore_digits & set(lst_n):
            continue
        flg = True
        for i in range(len(lst_n)):
            if not is_prime(int(''.join(lst_n))):
                flg = False
                break
            lst_n.append(lst_n.pop(0))
        if flg == True: cnt += 1
    return cnt

xxx@xxxxx:~$ time python3 before.py
real    0m5.649s
user    0m5.640s
sys     0m0.004s
xxx@xxxxx:~$ time python3 after.py
real    0m0.711s
user    0m0.708s
sys     0m0.000s

スーパー早くなったっす。