[基本情報技術者試験]ユークリッドの互除法のアルゴリズムをPythonで書いてみた。 - Qiita

概要 基本情報技術者試験の午後の試験でアルゴリズムがあります。過去問を解いても理解ができません…。実際にアルゴリズムをPythonで書いて、理解を深めていきたいと思います。 まず最初はユークリッドの互除法のアルゴリズムから書いてみます。 ユークリッドの互除法 アルゴリズム 二つの整数の大きい方から小さい方を引くことを、両者が等しくなるまで繰り返す。等しくなった値が最大公約数である。 GCMはGreatest Common Measure（最大公約数） コード # ユークリッドの互除法で最大公約数を求めるGCM関数 def GCM(A,B): # 繰り返し処理 while A != B: # AとBが等しくなるまで繰り返す print("A=",A,"B=",B) # 途中の結果 # 分岐処理 if A > B: # AがBより大きいなら A = A - B # AにA-Bを格納する els