最小公倍数と最大公約数

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

んーー。。

最大公約数（greatest common devisor）は言わずと知れたユークリッドの互除法で解けます。

まー一応ソースを載せるなら、

こんな感じ。

view plainprint?

1. int gcd(int a, int b) {  
2.     if (!b)  
3.         return a;  
4.     return gcd(b, a%b);  
5. }  

int gcd(int a, int b) {
    if (!b)
        return a;
    return gcd(b, a%b);
}

じゃー、最大公約数（least common multiple）は？

・・・・・

ちょっと迷った（笑）

でもちょっと考えてみると、a * bを出してa と bの共通の約数で割っていくと、lcmが出ることに気付く。

ということは、下のコードでイケますね！

view plainprint?

1. int lcm(int a, int b) {  
2.     return a*b/gcd(a,b);  
3. }  

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

今日は、若干手抜きな感がありますが、悪しからず。