【Python】素数計算プログラム

• 素数計算のプログラムを書きました
• 2パターン作成しました
  • ①数字を順番に見ていって、素数で割れるか判定
  • ②エラトステネスのふるいの実装
  • 高速なのは②です。結論だけ知りたい方はパターン②のコードをご覧ください
• 一通りの解説の後、今回まとめたコードになるまでの過程も載せます。お時間があればご覧ください。
• 1,000,000までの素数を計算して、時間を計測しました

パターン①：数字を順番に見ていって、素数で割れるか判定

• シンプルに数字を順番に見に行って、その数字が素数で割れるか判定する

コード

import datetime
import math

# input
upper_limit_num = 1000000

def calc_prime_num(upper_limit_num):
    # 2は素数のため追加
    list_prime_num = [2]

    # 3から順番に確認
    for num in range(3, upper_limit_num+1, 2):
        # 平方数まで確認すればOK
        limit = math.sqrt(num)
        is_prime = True
        # 確認した数までの素数で割れるか確認
        for prime_num in list_prime_num:
            # 必要ループ数以上で終了
            if prime_num > limit:
                break
            # 割り切れたら素数では無い。次の数へ
            if num % prime_num == 0:
                is_prime = False
                break
        # 割り切れなかったら新しく素数に追加
        if is_prime:
            list_prime_num.append(num)

    return list_prime_num

if __name__ == "__main__":

    start = datetime.datetime.now()
    list_prime_num = calc_prime_num(upper_limit_num)
    end = datetime.datetime.now()

    # 求めた素数をカレントディレクトリに出力
    with open ("./prime_num_list.txt", "w") as o:
        print(*list_prime_num, sep="\n", file=o)

    # 実行結果出力
    do_time = end - start
    print("実行時間：", do_time)
    print("素数の数：", len(list_prime_num))

処理内容

• 2は素数なので追加 → list_prime_num
• 3から順番にループ(上記コードだと3~1,000,000)
  • ここまでの素数リスト(list_prime_num)で割れるか確認
  • 割れる → 素数では無いので次の数へ
  • 割れない → 素数リスト(list_prime_num)に追加
  • ループは平方数まででOK
  • 例えば100で考える
    • 100を2つの数の掛け算で考えると組み合わせは
    • $100 \times 1$、$50 \times 2$、$25 \times 4$、$20 \times 5$、$10 \times 10$
    • 2つの数のうち小さい数は必ず平方数(今回は $\sqrt{100} = 10$)以下になる
    • そのため、確認は平方数までで良い

実行時間

• 10 ~ 1,000,000までの実行時間を測定

パターン②：エラトステネスのふるい

• 素数を調べる一般的な方法
• こちらの方が高速で計算できる

コード

import datetime

# input
upper_limit_num = 1000000

def calc_eratosthenes(upper_limit_num):

    # 上限の平方数まで確認すればOK
    loop_limit = upper_limit_num ** 0.5
    # 上限数のTrueリストを生成、indexを数で管理する
    list_sieve = [True] * (upper_limit_num + 1)

    # 0、1は素数ではないためFalse
    list_sieve[0] = False
    list_sieve[1] = False

    # 2~上限の平方数までを確認
    target_num = 2
    while target_num < loop_limit:
        # 素数(=True)の場合 → 倍数をFalseに
        if list_sieve[target_num] == True:
            for num in range(target_num*target_num, len(list_sieve), target_num):
                list_sieve[num] = False
        target_num = target_num + 1

    # Trueで残った数のみリストで出力
    list_prime_num = [index for index, flag in enumerate(list_sieve) if flag == True]
    return list_prime_num

if __name__ == "__main__":
    start = datetime.datetime.now()
    list_prime_num = calc_eratosthenes(upper_limit_num)
    end = datetime.datetime.now()

    # 求めた素数をカレントディレクトリに出力
    with open ("./prime_num_list.txt", "w") as o:
        print(*list_prime_num, sep="\n", file=o)

    # 実行結果出力
    do_time = end - start
    print("実行時間：", do_time)
    print("素数の数：", len(list_prime_num))

処理内容

• 求める上限までのTrueリスト(list_sieve)を生成
  • 1,000,000までの場合、1,000,001個のTrueのリストを作成
  • インデックス番号=数字として考える
  • この後、素数じゃない数字をFalseにしていく
• 0,1は素数ではないためFalse
• 2~求める上限の平方数までループ
  • リスト(list_sieve)の一番小さいインデックスが素数
  • 素数の倍数は素数ではないため、Falseにする
• Trueで残った数(index番号)をリストに出力 → list_prime_num

実行時間

• 10 ~ 1,000,000までの実行時間を測定

• 1,000,000の時にパターン①の1/8まで処理時間が低減
• 大きい影響は以下です
  • ループが少ない → N上昇に比例して処理時間が伸びにくい
  • bool型の処理が速い

最後に

• 素数を計算するパターン2つを共有しました
• ちょっとした思いつきで書いてみたのですが、想像以上に学びが多かったです
  • 考え方をコードとして実装する
  • 処理の効率化
  • リスト内包表記も苦手だったのですが、勉強して実装しました 笑

Appendix：パターン①・②になるまでの過程

• パターン①・②それぞれブラッシュアップして書きました
• 学びが色々あったので、その過程を記録します
• 計算のコードが知りたい場合は下記は不要です。お時間があり、気になる方のみご覧ください。

パターン①までの過程

①-1.何も考えずに実装

コード

import datetime

# input
upper_limit_num = 1000000

def calc_prime_num(upper_limit_num):
    list_prime_num = [2]

    for num in range(3, upper_limit_num+1):
        count = 1
        for prime_num in list_prime_num:
            if num % prime_num == 0:
                break
            if count == len(list_prime_num):
                list_prime_num.append(num)
            count = count + 1

    return list_prime_num

if __name__ == "__main__":

    start = datetime.datetime.now()
    list_prime_num = calc_prime_num(upper_limit_num)
    end = datetime.datetime.now()

    with open ("prime_num_list.txt", "w") as o:
        print(*list_prime_num, sep="\n", file=o)

    # 実行結果出力
    do_time = end - start
    print("実行時間：", do_time)
    print("素数の数：", len(list_prime_num))

実行時間

• 10 ~ 1,000,000までの実行時間を測定

①-2.①-1のコンセプトで最適化→パターン①

コード ※パターン①と同一

import datetime
import math

# input
upper_limit_num = 10

def calc_prime_num(upper_limit_num):
    # 2は素数のため追加
    list_prime_num = [2]

    # 3から順番に確認
    for num in range(3, upper_limit_num+1, 2):
        # 平方数まで確認すればOK
        limit = math.sqrt(num)
        is_prime = True
        # 確認した数までの素数で割れるか確認
        for prime_num in list_prime_num:
            # 必要ループ数以上で終了
            if prime_num > limit:
                break
            # 割り切れたら素数では無い。次の数へ
            if num % prime_num == 0:
                is_prime = False
                break
        # 割り切れなかったら新しく素数に追加
        if is_prime:
            list_prime_num.append(num)

    return list_prime_num

if __name__ == "__main__":

    start = datetime.datetime.now()
    list_prime_num = calc_prime_num(upper_limit_num)
    end = datetime.datetime.now()

    # 求めた素数をカレントディレクトリに出力
    with open ("./prime_num_list.txt", "w") as o:
        print(*list_prime_num, sep="\n", file=o)

    # 実行結果出力
    do_time = end - start
    print("実行時間：", do_time)
    print("素数の数：", len(list_prime_num))

①-1からの改善ポイント

• 素数かどうかの確認ループの効率化
  • range(3, upper_limit+1) → range(3, upper_limit+1, 2)
  • ループ数を低減
  • 偶数は素数にならないので、奇数のみをループ
• 追加：割り切れるかどうかはその数の平方数までを確認
  • ループ数を低減
• 割り切れるか確認したかを効率化
  • 変数countで個数を確認 → bool型is_primeで判定
  • この変更が一番速くなった

実行時間

• めっちゃ速くなってびっくりした。最適化は大事だなと勉強になりました(^_^;)

パターン②までの過程

②-1.何も調べずにエラトステネスのふるいを実装

• エラトステネスのふるいの原理だけを調べて実装

コード

import datetime
import sys

# input
upper_limit_num = 100000
loop_limit = upper_limit_num ** 0.5

def calc_prime_num(upper_limit_num):
    list_prime_num = []
    for input_num in range(2, upper_limit_num+1):
        list_prime_num.append(input_num)

    target_index = 0
    list_prime_num = calc_eratosthenes(target_index, list_prime_num)

    return list_prime_num

def calc_eratosthenes(target_index, list_prime_num):
    if list_prime_num[target_index] > loop_limit:
        return list_prime_num

    target_num = list_prime_num[target_index]
    for num in list_prime_num[:]:
        if num <= target_num:
            continue
        if num % target_num == 0:
            list_prime_num.remove(num)
    return calc_eratosthenes(target_index+1, list_prime_num)

if __name__ == "__main__":
    sys.setrecursionlimit(2000)

    start = datetime.datetime.now()
    list_prime_num = calc_prime_num(upper_limit_num)
    end = datetime.datetime.now()

    with open ("./prime_num_list.txt", "w") as o:
        print(*list_prime_num, sep="\n", file=o)

    # 実行結果出力
    do_time = end - start
    print("実行時間：", do_time)
    print("素数の数：", len(list_prime_num))

    print(sys.getrecursionlimit())

処理の概要

• 上限数までのリストを作成
• 小さい素数から順番に素数の倍数をリストから削除する
  • 素数の倍数を削除したリストを新しく作成
  • 再帰関数で作成したリストの引渡し・次の素数へ

実行時間

• 1,000,000だと再帰数が大きすぎて実行できず
• 「リストを新しく作り直す」「再起関数で大きいリストを渡す」がとにかく効率が悪い(^_^;)

②-2.リストで管理するコンセプトはそのままで処理内容を最適化

コード

import datetime

# input
upper_limit_num = 1000000

def calc_prime_num(upper_limit_num):

    list_prime_num = list(range(2, upper_limit_num+1))

    list_prime_num = calc_eratosthenes(list_prime_num)

    return list_prime_num

def calc_eratosthenes(list_prime_num):

    loop_limit = upper_limit_num ** 0.5
    target_index = 0

    while True:
        target_num = list_prime_num[target_index]
        if list_prime_num[target_index] > loop_limit:
            return list_prime_num

        list_prime_num = [num for num in list_prime_num if num == target_num or num % target_num != 0]
        target_index = target_index + 1

if __name__ == "__main__":
    start = datetime.datetime.now()
    list_prime_num = calc_prime_num(upper_limit_num)
    end = datetime.datetime.now()

    with open ("./prime_num_list.txt", "w") as o:
        print(*list_prime_num, sep="\n", file=o)

    # 実行結果出力
    do_time = end - start
    print("実行時間：", do_time)
    print("素数の数：", len(list_prime_num))

②-1からの改善ポイント

• 再帰関数をやめて、while True:を使用
• リストを新しく作成する処理をリスト内包表記で最適化

実行時間

• リストを新しく作成する方法は効率が悪い。

②-3.bool型でエラトステネスのふるいを実装

• 管理するリストをint型→bool型に変更

コード

import datetime

# input
upper_limit_num = 1000000

def calc_eratosthenes(upper_limit_num):

    loop_limit = upper_limit_num ** 0.5
    list_sieve = [True] * (upper_limit_num + 1)

    list_sieve[0] = False
    list_sieve[1] = False

    target_num = 2
    while True:
        if target_num > loop_limit:
            break
        if list_sieve[target_num] == False:
            target_num = target_num + 1
            continue
        if list_sieve[target_num] == True:
            for num in range(target_num*2, len(list_sieve), target_num):
                list_sieve[num] = False

        target_num = target_num + 1

    list_prime_num = [index for index, flag in enumerate(list_sieve) if flag == True]
    return list_prime_num

if __name__ == "__main__":
    start = datetime.datetime.now()
    list_prime_num = calc_eratosthenes(upper_limit_num)
    end = datetime.datetime.now()

    with open ("./prime_num_list.txt", "w") as o:
        print(*list_prime_num, sep="\n", file=o)

    # 実行結果出力
    do_time = end - start
    print("実行時間：", do_time)
    print("素数の数：", len(list_prime_num))

処理の概要

• bool型のリストを使って、素数 = True、素数じゃない = Falseで管理する

• while Trueでループ処理

  • 上限数の平方数になったら終了
  • 小さい素数から順番に、整数倍の数をFalseにする
  • すでにFalseの場合は素数じゃないためスキップ

• ※whileループ内の条件分岐が冗長(次で直ります)

処理時間

②-4.②-3を最適化 = パターン②

コード ※パターン②と同一

import datetime

# input
upper_limit_num = 10

def calc_eratosthenes(upper_limit_num):

    # 上限の平方数まで確認すればOK
    loop_limit = upper_limit_num ** 0.5
    # 上限数のTrueリストを生成、indexを数で管理する
    list_sieve = [True] * (upper_limit_num + 1)

    # 0、1は素数ではないためFalse
    list_sieve[0] = False
    list_sieve[1] = False

    # 2~上限の平方数までを確認
    target_num = 2
    while target_num < loop_limit:
        # 素数(=True)の場合 → 倍数をFalseに
        if list_sieve[target_num] == True:
            for num in range(target_num*target_num, len(list_sieve), target_num):
                list_sieve[num] = False
        target_num = target_num + 1

    # Trueで残った数のみリストで出力
    list_prime_num = [index for index, flag in enumerate(list_sieve) if flag == True]
    return list_prime_num

if __name__ == "__main__":
    start = datetime.datetime.now()
    list_prime_num = calc_eratosthenes(upper_limit_num)
    end = datetime.datetime.now()

    # 求めた素数をカレントディレクトリに出力
    with open ("./prime_num_list.txt", "w") as o:
        print(*list_prime_num, sep="\n", file=o)

    # 実行結果出力
    do_time = end - start
    print("実行時間：", do_time)
    print("素数の数：", len(list_prime_num))

②-3からの改善ポイント

• whileループ内の不要な条件分岐を削減
  • while True: → while target_num < loop_limit:
  • if target_num > loop_limit:をループ条件に変更
    • コードの簡潔化
  • if list_sieve[target_num] == False:を削除
  • Trueの場合のif文があれば、Falseの場合はスキップできるため、不要な条件分岐
• 素数の整数倍をFalseにするループの効率化
  • for num in range(target_num*2, len(list_sieve), target_num):
    → for num in range(target_num*target_num, len(list_sieve), target_num):
  • 開始の数を素数の2倍 → 素数の2乗に変更
  • ループ数の削減
  • 原理としては平方数までをループする場合と同様