[アルゴリズム]最大公約数、最小公倍数

780 ワード
テキストリンク
最大公約数と最小公約数を求める方法について
最大公約数(GCD)
2種類の自然水の共同薬水の中で最大の1種である.
最小公倍数(LCM)
2つの自然数の共通倍数のうち最小の数

最大公約数


方法。


確定->O(n)

方法2:ユークリッドアーク除去法


GCD(a, b) == GCD(b, a % b)
この性質を使用してa%b=0を繰り返します.残数が0の場合a,bの最大公約数で割る

コード#コード#

int GCD(int a, int b) {
    int remainder = a % b;
    if (remainder == 0) return b;
    else return GCD(b, remainder);
}

最小公倍数



LCM(a,b)=a*b/GCD(a,b)

コード#コード#

int LCM(int a, int b) {
    return a * b / GCD(a, b);
}
[TIL]悪魔ルート先端0809
Django ManyToMany