shiroの知恵袋

元SEのIT講師shiroが、プログラミングや趣味を語るブログです。

【プログラミング問題解答例】エラトステネスの篩(Python編)

↓問題はこちら↓
【プログラミング問題】エラトステネスの篩 - shiroの備忘録的メモ

解答例1

問題文のアルゴリズムに沿って、そのまま書いたものです。
初心者の方の練習用に使ってもらえたら嬉しいので、コメント付きです。
直観的なプログラムにはなっていると思います。が、激烈に遅いです。

# エラトステネスの篩
def sieve_of_eratosthenes(x):
    import math
    prime_list = []

    # 1. 探索リストに2から指定した値maxまでの整数を昇順で入れる。
    search_list = [i for i in range(2, x + 1)]

    # 3. 2の操作を探索リストの先頭値がmaxの平方根に達するまで行う。
    search_end_num = math.sqrt(x)
    while search_list[0] < search_end_num:
        # 2. 探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから削除する。
        check_num = search_list[0]
        prime_list.append(check_num)
        for i in search_list:
            if i % check_num == 0:
                search_list.remove(i)

    # 4. 探索リストに残った数を素数リストに移動する。
    prime_list += search_list

    return prime_list


# 素数リストを取得して表示する
prime_list = sieve_of_eratosthenes(10000)
for prime in prime_list:
    print(prime)

解答例2

解答例1が遅いのはリストのremoveとか使って何度も無駄な探索してるせいでしょ、、、
ということで速度重視で書き直してみたものです。

10万までの素数で実行時間を調べてみたところ、だいぶ改善されました。

解答例1:約23.9[sec]
解答例2:約0.6[sec]

まだ明らかに遅い箇所があればぜひ教えてください。

# エラトステネスの篩(高速版)
def sieve_of_eratosthenes_fast(x):
    import math
    judge_list = [True] * (x - 1)

    search_end_num = math.sqrt(x)
    check_num = 2
    while check_num < search_end_num:
        for n in range(check_num + 1, x + 1):
            if n % check_num == 0:
                judge_list[n - 2] = False
        for n in range(check_num + 1, x + 1):
            if judge_list[n - 2]:
                check_num = n
                break

    prime_list = []
    for i in range(2, len(judge_list)):
        if judge_list[i - 2]:
            prime_list += [i]

    return prime_list


# 素数リストを取得して表示する
prime_list = sieve_of_eratosthenes_fast(100000)
for prime in prime_list:
    print(prime)