【Python】素数の生成【整数論】

  • 2021年12月17日
  • 2022年8月1日
  • Python
  • 72View
  • 0件

はじめに

Python での素数ジェネレーターの実装例を紹介します。

素数とは、2以上の自然数で、他の数字で割り切ることができないような数を表します。
Python の yield を利用して、無限素数列のジェネレーターを作成します。

Wikipedia 素数

サンプルコード

サンプルコードと実行結果です。
ここでは、10回のループで止めています。
range の指定値を大きくすると、計算能力が追いつく限りはどこまでも素数を生成します。

戻り値を yield で指定することによって、関数の処理を一時停止させて無限リストを実現しています。

import itertools


def prime_numbers():
    ps = []

    def is_prime(n):
        for p in ps:
            if n % p == 0:
                return False
            if p ** 2 >= n:
                break
        return True

    for n in itertools.count(2):
        if is_prime(n):
            yield n
            ps.append(n)


if __name__ == '__main__':
    ps = prime_numbers()
    for _ in range(10):
        print(next(ps))
❯ python3 prime.py 
2
3
5
7
11
13
17
19
23
29

時間がかかりますが、以下は100万個目の素数の出力例です。

・・・(省略)・・・
15485621
15485651
15485653
15485669
15485677
15485689
15485711
15485737
15485747
15485761
15485773
15485783
15485801
15485807
15485837
15485843
15485849
15485857
15485863

おしまい!