Project Euler 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文は便利ですね。