求最大公约数和最小公倍数

【原创】

两个数a，b，求二者的最大公约数，传统朴素的想法大家肯定都懂，不多说，这里有一种算法叫欧几里得算法，思想：若a，b同时为0，那么最大公约数不存在，若，一个为0，那么最大公约数为另外一个不为0 的数，若a，b都不为0，则使新的a=b，新的b =a%b，然后重复使得b=0，此时的a为所求，至于这个算法的证明，可以去百度一下最大公约数的欧几里得算法证明，不过写两个数，自己笔算一下就出来了；

在求得最大公约数后，在求最小公倍数便十分的方便直接a*b／公约数

代码：这里提供了递归和迭代实现

#include<stdio.h>
//最大公约数方法,递归
int gcd_1(int a,int b){
    if (b==0) return a;
    else return gcd_1(b,a%b);
}
//最大公约数方法2
int gcd_2(int a,int b){
    while(b){
        int tmp = a%b;
        a = b;
        b = tmp;
    }
    return a;
}
int main() {
    int a,b;
    while (scanf("%d%d",&a,&b)!=EOF) {
   printf("%d
",gcd_1(a, b));//最大公约数
    printf("%d
",a*b/gcd_2(a,b));//最小公倍数
    }
    return 0;
}