DNCLでユークリッドの互除法を書く

はじめに

この記事は 共通テスト手順記述標準言語 (DNCL) Advent Calendar 2025 の２０日目の記事です。

DNCLでユークリッドの互除法を書きます。

ユークリッドの互除法とは

２数aとb(a ≧ b、b ≠ 0)の最大公約数がbと、aをbで割った余りの最大公約数に等しいことを利用した最大公約数の求め方です。
以下の操作を繰り返します。

1. 2つの整数 a と b（a ≧ b、b ≠ 0）が与えられたとき、a を b で割った余りを r とする（a = bq + r）
2. もし r が 0 ならば、b が最大公約数（GCD）である
3. そうでなければ、(a, b) を (b, r) に置き換え、同じ手順を繰り返す

詳しくはこちらをご覧ください。

ユークリッドの互除法を書こう

a ← 120
b ← 56
r ← 1
r != 0 の間、
|  r ← a % b
|  もし r == 0ならば
|  |  "最大公約数は" と b を表示する。
|  を実行する
|  a ← b
|  b ← r
を繰り返す