【杭电】[1108]最小公倍数

问题描述

最小公倍数

问题分析

基础的一种求最小公倍数
用乘积除以最大公约数
求最大公约数的方法……
话说学长说没听说过这种……
-.-

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include<stdio.h>
int main() {
    int a,b,m;
    while(scanf("%d %d",&a,&b)!=EOF) {
        m=a*b;
        while(a!=b) {
            if(a>b)
                a-=b;
            if(b>a)
                b-=a;
        }
        printf("%d\n",m/a);
    }
    return 0;
}

然后交给我一种更快速的递归函数
求最大公约数的

1
2
3
4
5
6
7
8
 int gcd(int a,int b)
{
if(b==0)
{
return a;
}
return gcd(b,a%b);
}

所以求最小公倍数的可以写成

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