ユークリッドの互除法を使った最大公約数を求めるプログラムを実装しました

ユークリッドの互除法を使って最大公約数を求めるPythonプログラムを実装しました。

###########################
## ユークリッドの互除法
##########################

input_line1 = input("MとNを、M Nの形式で入力してください\n")
array1 = input_line1.split(' ')
M = int(array1[0])
N = int(array1[1])
if M < N:
  tmp = N
  N = M
  M = tmp

while True:
  d = M % N
  if d == 0:
    print(N)
    break
  M = N
  N = d

試しに、M = 40 N = 16で実行します。

実際に計算すると

40 % 16 = 8
16 / 8 = 0
最大公約数は8ですね