こんにちは。今回もPythonのお勉強 問題集というサイトの問題を解いてみたので、知識の整理を兼ねてアウトプットしたいと思います。
今回は、任意の範囲の整数の中の素数を全て求める問題です。
#素数を求める
整数はその平方根よりも大きい素数では割ることができないという性質があります。今回はこの性質を利用していきます。
import math
prime_number_list = list()
def prime_number(start, end):
for i in range(start, end+1):
prime = True
if i == 1:
prime = False
for j in range(2, math.floor(math.sqrt(i))+1):
if i%j == 0:
prime = False
break
if prime:
prime_number_list.append(i)
return prime_number_list
print(prime_number(2, 1000))
math.sqrtを利用してiの平方根を算出し、j(2~√i+1の間の整数)でiを割ることでiが素数か否かを判定し、primeをTrue or Falseにします。prime=Trueのときにiは素数なので、prime_number_listにappendします。
iが1のときに関しては、iが素数と判定されると困る(1は2以上の整数で割り切れないため、prime=Trueと判定されてしまうから)ので、強制的にprime=Falseとセットしています。
###偶数を除外して処理スピードを速くする
一つ目のforループの時点で偶数を除外したいと思います。ただし、2は素数なので、startが1 or 2のときに2が素数になるようにセットしています。
import math
prime_number_list = list()
def prime_number(start, end):
##追加
if start < 3:
prime_number_list.append(2)
if start % 2 == 0:
start = start + 1
else:
start = start
##1つずつスキップしてrangeを設定
for i in range(start, end+1, 2):
prime = True
if i == 1:
prime = False
continue
for j in range(2, math.floor(math.sqrt(i))+1):
if i%j == 0:
prime = False
break
if prime:
prime_number_list.append(i)
return prime_number_list
print(prime_number(1, 1000))
#おわりに
偶数を飛ばすときに2を素数判定させるのが冗長になってしまったので、そこを改善したいです。なにか意見があればコメントよろしくお願いいたします!