使用的辗转相除法

辗转相除法：辗转相除法是求两个自然数的最大公约数的一种方法，也叫欧几里德算法。

例如，求（319，377）：

∵ 319÷377=0（余319）

∴（319，377）=（377，319）；

∵ 377÷319=1（余58）

∴（377，319）=（319，58）；

∵ 319÷58=5（余29）

∴ （319，58）=（58，29）；

∵ 58÷29=2（余0）

∴ （58，29）= 29；

∴ （319，377）=29。

可以写成右边的格式。

用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。最后所得的那个最大公约数，就是所有这些数的最大公约数。

代码

#include<stdio.h>
int main() {
    int maxgongyue(int x,int y);
    int mingongbei(int num,int finax);
    int x,y,num;
    printf("请输入俩个数:\n");
    scanf("%d %d",&x,&y);
    num=x*y;
    printf("最大公约数是:%d\n",maxgongyue(x,y));
    printf("最小公倍数是:%d\n",mingongbei(num,maxgongyue(x,y)));
    return 0;
}

int maxgongyue(int x,int y){
    int temp,yushu;
    if(x<y) {  //交换成大的在前，小的在后
        temp=x;
        x=y;
        y=temp;
    }
    while(y!=0) { //辗转相除法，如果余数不为0，则循环
        yushu=x%y;   //求余数
        x=y;         //将小的赋值给大的
        y=yushu;     //将余数赋值给小的
    }//一直除到余数为0时，这时候的x就是最大公约数
    return(x);
}

int mingongbei(int num,int finax){
    return(num/finax);
}