Help us understand the problem. What is going on with this article?

素数ジェネレータ(python)

More than 3 years have passed since last update.

素数を取得する処理が時々欲しくなるのでライブラリ化。
アルゴリズムはここのを参考にさせて頂きました。

指定最大値に応じたリストを作るため、大きい値を指定すると動かない。(マシンのメモリ搭載量による)
うちの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

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away