互いに素の数列
2つの数 \(a\) と \(b\) の最大公約数（GCD）が 1 のとき、\(a\) と \(b\) は互いに素です。 GCD とは、与えられた 2 つの数 \(a\) と \(b\) を割り切る最大の正の数のことです。たとえば、7 と 9 は GCD が 1 なので互いに素です。
2 つのリスト list1 と list2 が与えられたとき、list1 と list2 から互いに素の組をすべて含む新しいリスト coprimes を作成するのが課題です。
ただしその前に、次のアルゴリズムを使って GCD を求める関数を書いてください。
- \(b = 0\) か確認する
- 真なら、\(a\) を \(a\) と \(b\) の GCD として返す
- 偽なら、手順 2 に進む
- 代入を行う：$a \leftarrow b$、\(b \leftarrow a \% b\)
- 手順 1 に戻る
この演習はコースの一部です
Pythonでコーディング面接問題を練習する
実践的なインタラクティブ演習
このサンプルコードを完成させて、この演習に挑戦してみましょう。
def gcd(a, b):
# Define the while loop as described
while ____:
temp_a = ____
a = ____
b = ____
# Complete the return statement
return ____