演習課題「フェルマーテストを実装する」
整数nが入力として与えられるので、フェルマーテストによる素数判定をおこない、素数と判定されたらYESと、素数ではないと判定されたらNOと出力してください。
なお、パラメータaの値は2で固定するものとします。
右側のコードエリアには、入力nを受け取り、関数fermatTestに渡してフェルマーテストによる素数判定をおこなうコードが用意されています。関数fermatTestのコードを書き加え、コードを完成させてください。
期待する出力値
NO
※有料会員になるとこの動画をご利用いただけます
詳しい説明を読む
＃04:フェルマーテスト
このチャプターでは、素数かどうかを確率的に判定する「フェルマーテスト」というアルゴリズムについて学習します。
フェルマーテストは、フェルマーの小定理を利用しています。これは、「素数pと、pと互いに素である整数aについて、a^(p-1)をpで割った余りは1である」という定理です。
∗∗演算子を用いて、次のように求めることもできるfermat = a ** (n-1)
# 整数を受け取り、素数かどうかをフェルマーテストによって判定する関数
def fermatTest(n):
a = 2
if n % a == 0:
return False
fermat = 1
for _ in range(n-1):
fermat *= a
fermat %= n
return fermat % n == 1
n = 813
isPrime = fermatTest(n)
if isPrime:
print(f"{n} は素数")
else:
print(f"{n} は素数ではない")
ログインすると採点できます
コードの実行