演習課題「素数判定をおこなう」
整数nが入力として与えられるので、素数ならばYES
と、素数ではないならばNO
と出力してください。
右側のコードエリアには、入力を受け取って関数primalityTestに渡し、その返り値によってYES
とNO
を出力するコードが用意されています。関数primalityTestのコードを書き加え、問題を解くコードを完成させてください。
期待する出力値
YES
#02:高速な素数判定法
このチャプターでは、高速な素数判定法について学習します。
整数iが2以上√n以下であるということは、i^2が4以上n以下であることと同値です。したがって、for文とif文を合わせて、次のように書いてもよいです。この方法だと浮動小数点数がコードに登場しなくなるので、誤差について考慮する必要がなくなります。for i in range(2, n):
if i**2 > n:
break
# この下で素数判定をする
mathモジュールのsqrt関数を用いると平方根を求めることができます。math.sqrt(n)
また、∗∗演算子によっても求めることができます。n ** 0.5
import math
# 整数を受け取り、素数かどうかを判定する関数
def primalityTest(n):
if n == 1:
return False
for i in range(2, int(math.sqrt(n))+1):
if n % i == 0:
return False
return True
n = 813813813813
isPrime = primalityTest(n)
if isPrime:
print(f"{n} は素数")
else:
print(f"{n} は素数ではない")