Project Euler 035を解いてみる。「巡回素数」

Project Euler 035

035

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

->[次の問題]

考え方

以前に作成した素数の配列を返す関数で100万以下の素数を生成、forループで問題の条件に当てはまるか判定していきます。
判定の方法はi(1~素数の桁数-1)について、素数をi桁目で分け前後を入れ替えた数値を生成、生成した数値が素数の集合に含まれるか判定しました。
使用しているfor~else文では、forループを全て終了した場合のみelseの中が実行されるという仕様になっており、途中でループを抜ける場合にはelse内は実行されません。

# 例
num = '12345'
i = 3
print(num[i:]+num[:i])
# >>>45123

巡回素数を返す関数

euler035.py

def circular_primes(n: int) -> list:
    """n未満の巡回素数を返す関数
    Args:
        n: int
    Returns:
        list: n未満の循環素数の配列
    """
    # 自作の関数でn未満の素数の配列を取得
    prime_arr = get_prime_arr(n)
    # 素数判定用にsetも作成
    prime_set = set(prime_arr)
    result = []
    for p in prime_arr:
        # 素数をstr型へ変換
        p_str = str(p)
        # iは桁をずらす数(例 i = 2: 12345->34512)
        for i in range(1, len(p_str)):
            # スライスを使って素数を前後に切り分け、前後を入れ替える
            # 入れ替えてできた数値が素数に含まれなければループを抜ける
            if int(p_str[i:] + p_str[:i]) not in prime_set:
                break
        # ループを完遂する=すべて素数であった場合、resultに追加
        else:
            result.append(p)
    return result

コード

euler035.py

from math_functions import get_prime_arr


def main():
    print(len(circular_primes(10 ** 6)))


def circular_primes(n: int) -> list:
    """n未満の巡回素数を返す関数
    Args:
        n: int
    Returns:
        list: n未満の循環素数の配列
    """
    # 自作の関数でn未満の素数の配列を取得
    prime_arr = get_prime_arr(n)
    # 素数判定用にsetも作成
    prime_set = set(prime_arr)
    result = []
    for p in prime_arr:
        # 素数をstr型へ変換
        p_str = str(p)
        # iは桁をずらす数(i = 2: 12345->34512)
        for i in range(1, len(p_str)):
            # スライスを使って素数を前後に切り分け、前後を入れ替える
            # 入れ替えてできた数値が素数に含まれなければループを抜ける
            if int(p_str[i:] + p_str[:i]) not in prime_set:
                break
        # ループを完遂する=すべて素数であった場合、resultに追加
        else:
            result.append(p)
    return result


if __name__ == '__main__':
    main()

pythonのスライス、for~else文は便利ですね。