最大公約数と最小公倍数(GCD、LCM)

2563 ワード
JavaScript TIL テキストリンク
プログラマーの最大公倍数と最小公倍数問題を解決した後、他の開発者の解答を見て、自分の目を疑った.
問題を見る前に,最大公約数と最小公倍数(GCD,LCM)について簡単にまとめてみよう.
2つの整数a、bの承諾数は、aの約数およびbの約数の整数であり、公倍数は、aおよびbの倍数の整数である.
このとき,最大公約数(GCD,Great Common Divisor)は最大公約数を意味する.
最小公倍数(LCM,LeastCommon Multiple)は最小公倍数を表す.
ユークリッドアーク除去法(Euclidean Algorithm):aをbで除算し、残りがrの場合、GCD(a, b) = GCD(b, r)が成立する.
function gcdlcm(a, b) {
  var r;
  for(var ab= a*b;r = a % b;a = b, b = r){}
  return [b, ab/b];
}
ドアがどのように回っているのか気になったので、頭の中でゆっくり思い出しました.
宣言(var ab = a*b)
宣言値aにbを乗じる変数abに割り当てられる.
条件文(r = a % b)
この部分はこのコードの花と見なすことができる.
条件文の値がtrueの場合、繰り返し文が実行され続け、r = a % bに対する出力値がa % bであるため、値が0でない場合、trueとみなされ、aがbで除算された場合、繰り返し文は終了する(a%b=0).
増監門(a = b, b = r)
ユークリッド湖製法ではGCD(a, b) === GCD(b, a % b)の部分と言える.(条件文中r = a % b)
コンテンツソース:https://torbjorn.tistory.com/244
サムネイルソース:https://velog.io/@jelkov/Algorithm-with-Math-GCD-LCM
Credentials
C#汎用:Visitorモードのサイクル依存性を解消し、退屈なAcceptメソッド