素数を取得する処理が時々欲しくなるのでライブラリ化。
アルゴリズムはここのを参考にさせて頂きました。
指定最大値に応じたリストを作るため、大きい値を指定すると動かない。(マシンのメモリ搭載量による)
うちのPC環境(メモリ8GB)では10,000,000指定までは動き、100,000,000指定だと固まりました。。
(2016/9/27修正)
エラトステネスのふるいの論理により、指定最大値の平方根を超える値については、素数判定のリストを更新する必要がないことが分かったので、処理見直し。
prime.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import time
def primes(max_number):
"""
指定値未満の素数を取得するジェネレータ
:param max_number: 最大値
:return: 素数ジェネレータ
"""
if max_number <= 2:
raise StopIteration
yield 2
is_prime = [1] * max_number
square_root_of_max = max_number ** 0.5
for number in range(3, max_number, 2):
if is_prime[number] is 0:
continue
yield number
if number <= square_root_of_max:
for multiple in range(number * 2, max_number, number):
is_prime[multiple] = 0
if __name__ == '__main__':
while True:
input_number = int(input("指定値未満の素数を列挙します。指定値:"))
start_time = time.time()
for prime in primes(input_number):
print(prime)
elapsed_time = time.time() - start_time
print("elapsed time:{0}".format(elapsed_time) + "[sec]")
おまけ:
自分で実装した素数取得処理。
実行速度が参考にしたサイトのものより遅かったので不採用。
prime_old.py
def primes(max_num):
if max_num <= 2:
raise StopIteration
yield 2
non_primes = set(range(2 * 2, max_num, 2))
for num in range(3, max_num, 2):
if num in non_primes:
continue
yield num
non_primes.update(range(num * 2, max_num, num))
else:
raise StopIteration
参考:
http://ami-gs.hatenablog.com/entry/2014/02/09/204205
https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9