最大公約数の求め方(互除法による)
Copyright (C) virtual_high_school, 2017

自然数a と b の最大公約数 GCM (a, b) の求め方

【音声入り動画による説明】

【パラパラ・マンガによる説明】
←パラパラまんが

【アルゴリズム】

1. a, b をそれぞれ被除数と除数にセットする。(大小どちらをどっちにセットしてもよい。)
2. 被除数 a を除数 b で割り、商 q と余り r を求める。ここでもし割り切れたら計算終了。このときの除数が最大公約数。
3. b を被除数 a に、r を除数 b にセットする。すなわち a:=b, b:=r
4. 2. に戻る。