【java】最大公約数、最小公倍数 コードテンプレ

【java】最大公約数、最小公倍数 コードテンプレ

最大公約数 greatest common divisor

static long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}


a=10, b=40
→40, 10(10%40)
→10, 0(40%10) => return 10 :10と40の最大公約数は10

最小公倍数 least common multiple

static long lcm(long a, long b) {
return a * b / gcd(a, b);
}


a=6, b=9
→54 /(gcd(6,9))
    gcd(6,9)=
    →6, 9
    →9, 6(6%9)
    →6, 3(9%6)
    →3, 0(6%3) => gcd = 3
→54 / 3 = 18 => return 18 : 6と9の最小公倍数は18


Javaカテゴリの最新記事