C语言多种方法求最大公因数和最小公倍数-Toy模板网

这篇具有很好参考价值的文章主要介绍了C语言多种方法求最大公因数和最小公倍数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

最大公约数：指能够整除多个整数的最大正整数，而多个整数不能都为零。

最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。

求最小公倍数的算法：

最小公倍数 = 两个整数的乘积 / 最大公因数

求最大公约数的算法：

第一种方法：辗转相除法

有两个整数a和b:

1. a % b ==temp;

2. 若temp = 0；那么b就是最大公约数。

3. 若temp ≠ 0；则a = b；b = temp；继续进行a % b 操作。

eg：求25和15的最大公约数，其过程为：

25 % 15 余 10 ； 15 % 10 余 5 ； 10 % 5 余 0 。因此5即为最大公约数

#include<stdio.h>
int main()
{
    int a  , b  , temp;
    printf("put in a and b : ");
    scanf("%d %d",&a,&b);
    int nul = a * b;
    
    while (a * b != 0)
    {
        temp = a % b;
        a = b;
        b = temp;
    }
    printf(" max = %d:",a);
    printf(" min = %d:", (nul / a)  );
    return 0;
}

put in a and b : 25 15
 max = 5: min = 75:

第二种方法：相减法

取两个整数a、b：

1. 若a > b,则 a = a - b；

2. 若a < b,则 b = b - a；

3. 若 a = b,则 a(b)即为两数的最大公约数

4.若 a ≠ b,则继续执行第一步操作。

eg：求25和15的最大公约数，其过程为：

25 - 15 = 10(15 > 10);15 - 10 = 5(10 > 5);

10 - 5 = 5(5 == 5)

因此，25 和15的最大公约数为5。

代码如下：

#include<stdio.h>
int main()
{
    int a , b , m , n;
    printf("put in a and b:");
    scanf("%d %d", &a, &b);
    m = a;
    n = b;
    while (a != b)
    {
        if(a > b)
        {
            a = a - b;
        }
        else
        {
            b = b - a;
        }
    }
    printf("max = %d\n", a);
    printf("min = %d",(m * n)/a);
    return 0;
}

运行结果展示：

put in a and b:25 15
max = 5
min = 75

第三种方法：穷举法

有两个整数a和b：

1. 令 i = 1，

2. 如果 a，b能同时被i整除，则h = i；

3. i++；

4. 若 i <= a(b)，则继续执行第2步操作；

5. 若i > a(b)，当 i = a(b)时，穷举结束，则此时h即为最大公约数。

代码如下

#include<stdio.h>
int main ()
{
    int a , b , m , n , i , h;
    printf("put in a and b:");
    scanf("%d %d", &a, &b);
    m = a;
    n = b;
    for( i = 1; i <= a; i ++)
    {
        if( a % i == 0 && b % i == 0)
        {
            h = i;
        }
    }
    printf("max = %d\n", h);
    printf("min = %d",(m * n) / h);
    return 0;
}

运行结果展示：文章来源地址https://www.toymoban.com/news/detail-452360.html