Search on the blog

2010年9月9日木曜日

最小公倍数と最大公約数

自数数a, b (a > b)の最小公倍数と最大公約数を求めるプログラムを作成せよ。

んーー。。

最大公約数(greatest common devisor)は言わずと知れたユークリッドの互除法で解けます。
まー一応ソースを載せるなら、
こんな感じ。


int gcd(int a, int b) {
    if (!b)
        return a;
    return gcd(b, a%b);
}
じゃー、最大公約数(least common multiple)は?

・・・・・

ちょっと迷った(笑)
でもちょっと考えてみると、a * bを出してa と bの共通の約数で割っていくと、lcmが出ることに気付く。
ということは、下のコードでイケますね!

int lcm(int a, int b) {
    return a*b/gcd(a,b);
}
今日は、若干手抜きな感がありますが、悪しからず。

0 件のコメント:

コメントを投稿