【プログラミング問題解答例】エラトステネスの篩(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)