寻找最大公约数和最小公倍数的碾转法(欧几里得算法)！

题目：输入两个正整数m和n，求其最大公约数和最小公倍数

int main()
{
    int a,b,num1,num2,temp;
    pritnf(“Please input two integers:\n”);
    scanf(“%d,%d”,&num1,&num2);
    if(num1    {
        temp=num1;
        num1=num2;
        num2=temp;
    }
    a=num1;
    b=num2;
    while(b!=0)
    {
        temp=a%b;
        a=b;
        b=temp;
    }
    printf(“Gongyueshu:%d\n”,a);
    printf(“Gongbeishu:%d\n”,num1*num2/a);
    return 0;
}

这个定理的意思是：整数m、n的最大公约数等于n和m除以n的余数的最大公约数。

这里假设m一开始大于n。m中可以含一个或者多个n，这些多个n并不影响m和n的最大公约数，所以需要把这些个n去掉，也就是得到 temp=m%n。此时temp一定小于n，所以同样的道理再求m=n，n=temp，temp=m%n，一直循环下去，直到temp=0，也就是说m可以整除n，此时上次循环后m就是最大公约数。

最小公倍数=两数相乘/最大公约数

python实现代码:

def gcd(m, n):
    while n:
        m, n = n, m % n
    return m