ユーグリットの互除法を使って最大公約数と最小公倍数を計算してみた

ユーグリットの互除法とは

最大公約数を求める手法のアルゴリズム。
2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。
引用：WikiPedia
イメージとしてこちらのサイトの図解が分かりやすいです。

.py

 a=1112
 b=695
 #最大公約数
 def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a
 print(gcd(a,b))
 
 #最小公倍数
 def lcm(a,b):
  return a*b//gcd(a,b)
 print(lcm(a,b))

# >>>139
# >>>5560