ユークリッドの互除法

atcoder復習＆勉強記録

問題①

問題、出力

解答コード

def GCD(n_1, m_1):
    while n_1 >= 1 and m_1 >= 1: # 余りが0になるまで繰り返す。
        if n_1 < m_1: # どっちが大きいのか確認
            m_1 = m_1 % n_1
        else:
            n_1 = n_1 % m_1 # mod(余りをセットする)
            
    if n_1 >= 1:
        return n_1
    else:
        return m_1
n, m = map(int, input().split())
print(GCD(n, m))

ユークリッドの互除法

2 つの自然数 a,b (a>b) について、a を b で割ったときの商を q、余りを r (≠0) とすると、「a と b の最大公約数」は、「b と r の最大公約数」に等しい。

コード説明

while文で渡された引数が0になるまで繰り返し処理を行う。
while文で行っている処理は大きい方の数を小さい数で割りその余りを変数にセットしている。

変数が0になったらwhile文を抜けて1より大きい数になっているものをif文で条件分岐をしてreturnを返している。

以上になります。