[数据结构与算法]辗转相除法求最大公约数和最小公倍数

辗转相除法，欧几里得算法是用来求两个正整数最大公约数的算法。古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法。

算法思路：先找出俩个数最大的数a，用最大的数对小的数b取余，a%b若余数r不为0，则将除数作为新的被除数，余数给新除数。循环直到余数r为0，则最后一次运算的除数则为最大公约数。

?

假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：

1997 / 615 = 3 (余 152)

615 / 152 = 4(余7)

152 / 7 = 21(余5)

7 / 5 = 1 (余2)

5 / 2 = 2 (余1)

2 / 1 = 2 (余0)?

至此，最大公约数为1

?

流程图如下：

?

?算法实现

C实现：

#include<stdio.h>
int main()
{
    int a,b,t,r,n;
    printf("请输入俩个数 a b\n");
    scanf("%d %d",&a,&b);
    if(a<b)  //假设 a=12，b=16，此时a>b,将a，b 交换位置， 将大的放在前面，换位置之后a=16，b=12。 
    {t=b;b=a;a=t;}
    r=a%b;  //这里的余数为4。 
    n=a*b;  //n=12*16 
    while(r!=0)   //第一次r=4，不等于0，进入 
    {
        a=b;  //第一次 a=b=12.
        b=r;  //第一次 b=4.
        r=a%b;//第一次 r=0; 则不会进入下一次   最小公倍数就是b 
    }
    printf("最大公约数是%d，最小公倍数是%d\n",b,n/b);
    
    return 0;
}

java实现

import java.util.Scanner;

public class TossAndTurnAndDivide {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        System.out.println("请输入俩个数");
        int a = in.nextInt();
        int b = in.nextInt();
        int t,r,n;
        if(a<b)
        {t=b;b=a;a=t;}
        r=a%b;
        n=a*b;
        while(r!=0)
        {
            a=b;
            b=r;
            r=a%b;
        }
        System.out.println("最大公约数是"+b+"最小公倍数是"+n/b);
    }
}