求最大公约数与最小公倍数（C语言）

一、题目

写两个函数，分别求两个整数的最大公约数和最小公倍数，用主函数调用这两个函数。两个整数由键盘输入。

二、分析及代码

1.思路

• 最大公约数：两个或多个整数共有约数中最大的一个。利用辗转相除法计算。
• 最小公倍数：两个或多个整数共有倍数中除0外最小的一个。由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积，所以，两个数的最小公倍数等于这两个数的乘积除最大公约数。
• 分析思路：分别定义两个函数，和两个变量a,b。第一个函数用辗转相除法求a,b的最大公约数，假设a>b，令a/b得到余数r，再将b作为被除数，r作为除数，得到余数…直至余数为0。第二个函数利用上述公式可求得两个数的最小公倍数。

2.代码

代码如下：

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int Greatest_Common_Divisor(int a,int b);       //函数声明
    int Least_Common_Multiple(int a,int b,int m);  //函数声明
    int a,b,m,x;
    scanf("%d,%d",&a,&b);
    m=Greatest_Common_Divisor(a,b);
    x=Least_Common_Multiple(a,b,m);
    printf("%d和%d的最大公约数是:%d\n",a,b,m);
    printf("%d和%d的最小公倍数是:%d\n",a,b,x);
    return 0;
}

int Greatest_Common_Divisor(int a,int b)  //求最大公约数
{
    int temp,r;
    if(b>a)             //让两个数中较大的数作为被除数
    {
        temp=a;
        a=b;
        b=temp;
    }
    while((r=a%b)!=0)
    {
        a=b;            //使除数b变为被除数a
        b=r;            //使余数r变为除数b
    }
    return b;
}

int Least_Common_Multiple(int a,int b,int m)  //求最小公倍数
{
    return (a*b/m);
}

3.运行结果