【アルゴリズムの勉強】Pythonでユークリッドの互除法を書いてみた
学習エントリ。
Pythonでユークリッドの互除法を実装する。
ユークリッドの互除法ってなんぞ
ユークリッドの互除法(ユークリッドのごじょほう、英: Euclidean Algorithm)は、2 つの自然数の最大公約数を求める手法の一つである。
2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。
明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第 7 巻、命題 1 から 3 がそれである
# coding: utf-8 x = 108 y = 648 def gcd(x,y): while y != 0: x , y = y , x % y return x print(gcd(x,y)) ##108