最大公因数GCD-ユークリッドアーク除算(+最小公倍数)

ユークリッドアークほう
2つの自然数の最大承諾数のアルゴリズムを求めます
2つの自然数a,b(a>b)がaをbで割った残りの数をrと呼ぶ場合、GCD(a,b)=GCD(b,r),「rが0の場合、bは最大公約数である.」この原理を利用したアルゴリズム.
GCD(24,16)=GCD(16,8)=GCD(8,0)GCD(24,16)=GCD(16,8)=GCD(8,0)GCD(24,16)=GCD(16,8)=GCD(8,0)
最大公約数=8
インプリメンテーション
💜 さいきかんすう

def GCD(a,b) :
  if b == 0 : return a
  else : return GCD(b,a%b)

💜 複文

def GCD(a,b) :
  while True :
    r = a % b
    if r == 0 : return b

    a = b; b = r

時間の複雑さ
O(logN)O(logN)O(logN)
最大公倍数
GCDを求めるコードを記述すれば,最大公倍数が容易に得られる.

def LCM(a,b) :
  return a*b/GCD(a,b)

参考文献
https://coding-factory.tistory.com/599