pythonでエラトステネスの篩を実装してみた

pythonとアルゴリズムの勉強かねがね、素数判定器「エラトステネスの篩」版を実装してみました。

↑だと14～15桁までの数値が素数かどうか1秒以内で判定できるのですが、複数値の素数確認をする場合はいちいち割り算をし直すため処理時間がかさんでしまいます。

AtCoder Beginner Contest 084
D - 2017-like Number
https://atcoder.jp/contests/abc084/tasks/abc084_d

こちらの過去問では「要求を満たす素数の数」が求められるため、「要求範囲内にある素数を導出」という用途のロジックを作成した…というのが今回の実装です。

10 ** 5までの素数を0.3～0.4秒程度で導出できましたので、とりあえず満足です。

※指定値がnp.arrayの対象外になっていたので修正しました。

sieve_of_eratosthenes.py

import datetime
import numpy as np

def sieve_of_eratosthenes(numbers):
    """指定された値までの素数を導出する関数.
    戻り値：
    素数のリスト
    """
    # 2から指定値までのndarrayを作成
    checker_np = np.array(range(2,numbers + 1))

    # 素数を格納するリストを作成
    prime_list = []

    while len(checker_np) != 0:
        # リストの先頭（この値は必ず素数）を抽出
        _x = checker_np[0]
        # 取り出した値を素数リストに格納
        prime_list.append(_x)
        # ndarrayの中身のうち、抽出した素数で割り切れる値を除外
        # ※先頭の値が必ず最小の素数になる
        checker_np = np.delete(checker_np, np.where(checker_np % _x == 0))

    return prime_list

# 入力値
numbers = 10 ** 5

start_time = datetime.datetime.now()
print(sieve_of_eratosthenes(numbers))
end_time = datetime.datetime.now()

# 処理速度を確認
print(end_time - start_time)