最小公倍数をjavaで求める 2007/09/06 2007/09/06

インターネットで調べればすぐにでてくると思いますが、とりあえず。

最小公倍数 - Wikipedia
を参考にしてみます。



えーと、
gcdは最大公約数 GCD (Greatest Common Divisor)というものらしいです。

API標準のBigIntegerに、gcdというメソッドがありますね。
これを利用して、
最小公倍数は、LCM (Least Common Multiple)を求めてみます。

ユーティリティメソッドにしてみました。

static public BigInteger gcd(BigInteger l, BigInteger r){
return l.gcd(r);
}

static public BigInteger lcm(BigInteger l, BigInteger r){
return l.multiply(r).divide(gcd(l, r));
}

複数の数の最小公倍数を求めるユーティリティメソッドです。上記のメソッドと一緒に使います。
再帰がかっこいいだろうなぁと思ったのですが、すぐに思いつかなかったので、下記のようにループにしてます。java5から導入された可変長引数を使用しています。便利だなぁと思いましたよ可変長引数。

static public BigInteger lcm(BigInteger l, BigInteger... rs){
BigInteger b = l;
for(BigInteger r:rs){
b = lcm(b, r);
}
return b;
}

使い方は、

BigInteger b2 = BigInteger.valueOf(3);
BigInteger b3 = BigInteger.valueOf(2);
BigInteger b4 = BigInteger.valueOf(4);
BigInteger b5 = BigInteger.valueOf(5);
System.out.println(lcm(b2, b3, b4, b5));

gcmを標準APIで間に合わせましたが、実装が気になるところです。