ちょっとPython - 素数を判定 -1
プログラミングで素数の判定をします。まず素数とは
素数とは2以上の"1"と対象となる数字(その整数自身)以外のもので割り切れないもの。
2,3,7,11・・・・ 素数
素数を判定するプログラムを作ります。まず日本語で作ってみます。
調べたい対象の数字を"n"とする
素数は2よりも小さい数は素数でない
2から"n"の一つ前までの数字で"n"を割って割り切れると素数ではない
"n"が割り切れない場合は素数
これをpythonのコードに置き換えます
def isPrime(n):
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return Trueこのコードを実行して出力します。
print(isPrime(7))
print(isPrime(8))True
False
"7"は素数(True)で"8"は素数でない(False)と出てきました。
日本語とコードを並べてみます。
調べたい対象の数字を"n"とする ・・・ def isPrime(n):
素数は2よりも小さい数は素数でない ・・・ if n < 2: return False
2から"n"の一つ前までの数字で"n"を割って割り切れると素数ではない
・・・ for i in range(2, n): if n % i == 0: return False
"n"が割り切れない場合は素数 ・・・ return True
このコードですが大きな数、10の9乗となると計算スピードがかなり落ちるということです。こんな大きな数を計算することは通常ないのですが、この世界ですとスピードが求められる場合があります。
高速化するには
n が合成数（素数でない数）のとき、2 から √n までの数で割り切れるかどうかを確認すればよいことが知られています。
これを使います。√nは"n**0.5"で計算できるので
def isPrime(n):
if n < 2:
return False
for i in range(2, n**0.5):
if n % i == 0:
return False
return Trueとするとエラーがでます。"n**0.5"は整数出ないので実行できないというエラーなので、整数にしてやります。"int(n**0.5)"とします。
def isPrime(n):
if n < 2:
return False
for i in range(2, int(n**0.5)):
if n % i == 0:
return False
return Trueこれで大丈夫かな？
print(isPrime(7))
print(isPrime(8))を実行すると両方ともTrueになります。実はint(n**0.5)すると切り捨てられるので必要な数にが足らなくなる場合があります。なので
def isPrime(n):
if n < 2:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True"+ 1"してやるます。これでうまく行きます。