概要
素数の列挙に関しては多くのアルゴリズムが考案されていますが、ある自然数が自身以下の素数で割り切れるかを判定することで素数判定を行う実装例を記載します。ナイーブな実装なのでそれなりに低速ですが、大体10^5以下の素数であればこれで列挙できるかと思います。
実装例
# 自然数m以下の素数を返す
def prime_numbers(m):
# 素数を保持するset
primes = set()
# 2以上m以下の素数を数え上げる
n = 2
while n <= m:
# 自身より小さい全ての素数で割り切れなければ、素数とみなせる
if all(n % i != 0 for i in primes):
primes.add(n)
n += 1
return primes
実行結果
# m = 100の場合
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}