解説
最大公約数（GCD）は、2つの整数を割り切れる最大の数です。ユークリッドの互除法を使うと一気に速くなります。約2300年前から知られる、最も古いアルゴリズムの一つです。
原理は「a と b の最大公約数は、b と (a を b で割った余り) の最大公約数に等しい」というものです。
手順はこれだけです。
1. a を b で割った余り r を求める。
2. a に b を、b に r を代入する。
3. b が 0 になったら、そのときの a が答え。
書き方
ユークリッドの互除法: gcd(a, b) = gcd(b, a % b)。 ・while b != 0: a, b = b, a % b（余りで置き換え）。 ・b が 0 になったときの a が最大公約数。 ・for a, b in pairs: でタプルのリストを分解して反復。
書いて動かす
この回の課題
2つの整数の最大公約数を、余りで置き換える互除法（while）で求めて表示してみよう。
コードはあなたの端末の中だけで動きます（サーバーには送られません）。進み具合もこのブラウザに保存されます。
自分のPCでも続けてみませんか
Windows版 InsightPy は Python を同梱しているので、環境構築なしで同じコードを書いて実行できます。 書いたコードを保存しておけるほか、ステップ実行で変数の変化を1行ずつ確かめられます。 個人の学習や私的な目的でのご利用は、31日目以降も無料です（スクリプトの保存は10本まで）。 このブラウザ版の学習センターも、引き続き無料でお使いいただけます。