WANTED:
より良い方法があればぜひ教えてください…！
前回
前回からの改善点
改善1
前回の記事で
-
allやanyのメソッドを使うと良い - 関数化すると良い
とコメントをいただきました。
import time
def primes_up_to_(upper_limit): # 関数化
if upper_limit < 2:
return []
primes_list = [2] # このリストに素数を保存していく、偶数は2だけが素数
for integer in range(3, upper_limit + 1, 2): # 3以上の奇数に対して、
if all(integer % prime != 0 for prime in primes_list): # 全てのprimeで割り切れなければ
primes_list.append(integer) # integerを素数として認め、primesに追加する
return primes_list
start_time = time.time() # 開始時刻を記録
primes_list = primes_up_to_(10000) # テキトーな上限値を指定し素数を探索
elapsed_time = time.time() - start_time # 経過時間 = 現在時刻 - 開始時刻
print(primes_list)
print(len(primes_list), "prime numbers foud.")
print ("run time: {0}".format(elapsed_time) + " seconds")
よりコンパクトになりました。allなどのメソッドは知らなかったので、コメントをいただけて光栄です。
integerを2つ飛ばしにしているので計算時間も少し短くなりました。
改善2
前回は安直にある自然数について、それより小さい素数で割り切れなければ、その自然数は素数であると思って素数を求めていましたが、本家エラトステネスのふるいの
愚直な方法
1：$1$から$n$まで順々に素数かどうか判定する。
2：$k$が素数かどうかは$\sqrt{k}$以下の素数たちで割り算すればよい。
の２の条件を知りませんでした。
2で$\sqrt{k}$が登場したのは$k$が合成数なら必ず$\sqrt{k}$より小さい素因数を持つからです。
はえ〜（バカ）。
これを前回のコードに盛り込むとこのようになりました。
import time
import math
primes_list = [] # このリストに素数を保存していく
upper_lim = 10000 # テキトーな数を設定
start_time = time.time() # 開始時刻を記録
for integer in range(2, upper_lim + 1, 1): # 2-10000の整数に対して、
if len(primes_list) < 1 : # primes_listが空だったら、
primes_list.append(integer) # primes_listにinteger(=2)を追加する
else: # その他の場合、
is_divisible = False # integerが割り切れない、つまり素数であることを仮定する
for prime in primes_list: # 今までに保存された全ての素数"prime"について、
if prime >= math.sqrt(integer): # integerの平方根よりprimeが大きければ、
break # もうこのforはやる意味がないです。
elif integer % prime == 0: # integerがprimeで割り切れるならば素数じゃないので、
is_divisible = True # 割り切れます
break # もうこのforはやる意味がないです。
# integerが合成数ならどっかのprimeでis_divisible = Trueになる
if not is_divisible: # すべてのprimeについてこの判定をしたのち、それでもなおis_divisible = Falseならばもうそれは素数
primes_list.append(integer) # integerを素数として認め、primes_listに追加する
print(primes_list)
print(len(primes_list), "prime numbers foud.")
elapsed_time = time.time() - start_time # 経過時間 = 現在時刻 - 開始時刻
print ("run time: {0}".format(elapsed_time) + " seconds")
前回のものでは$10^6$までの探索に4分くらいかかっていたのが、これを実行すると3.5秒くらいになりました。前回のやつだと$10^7$までの探索は数時間かかると見越していたのですが、今回のこれだと1分くらいで終わってしまいました。
古代ギリシャってやっぱすごい。
改善3
改善1 + 改善2です。
import time
import math
def primes_up_to_(upper_limit): # 関数化
if upper_limit < 2:
return []
primes_list = [2] # このリストに素数を保存していく、偶数は2だけが素数
for integer in range(3, upper_limit + 1, 2): # 3以上の奇数に対して、
temp_primes_list = [] # 追加
for prime in primes_list: # 追加
if prime <= math.sqrt(integer): # 追加
temp_primes_list.append(prime) # 追加
if all(integer % prime != 0 for prime in temp_primes_list): # 全てのprimeで割り切れなければ
primes_list.append(integer) # integerを素数として認め、primesに追加する
return primes_list
start_time = time.time() # 開始時刻を記録
primes_list = primes_up_to_(10000) # テキトーな上限値を指定し素数を探索
elapsed_time = time.time() - start_time # 経過時間 = 現在時刻 - 開始時刻
print(primes_list)
print(len(primes_list), "prime numbers foud.")
print ("run time: {0}".format(elapsed_time) + " seconds")
うーん、forループが増えてしまったせいで逆に処理時間が長くなってしまいました。