C语言中求公约数和公倍数的多种方法详解

创作时间:

作者:

@小白创作中心

C语言中求公约数和公倍数的多种方法详解

引用

来源

https://docs.pingcode.com/baike/1099707

在C语言中，求解公约数和公倍数是常见的基本操作。掌握这些方法，不仅有助于提升编程能力，还能为解决更复杂的问题打下坚实的基础。本文将详细介绍几种常用的求解方法，包括辗转相除法、利用公式计算以及使用循环和条件语句实现，并提供具体的代码示例。

一、辗转相除法求最大公约数

辗转相除法（Euclidean algorithm）是求两个整数最大公约数（GCD）的高效算法。其基本思想是：两数的最大公约数等于其中较小的那个数与较大数除以较小数的余数的最大公约数。

1、算法原理

假设有两个整数a和b（a > b），用a除以b，得到余数r；
将b作为新的a，将r作为新的b，重复上述步骤，直到r为0；
当r为0时，b即为a和b的最大公约数。

2、代码实现

#include <stdio.h>

// 求最大公约数的函数  
int gcd(int a, int b) {  
    while (b != 0) {  
        int temp = b;  
        b = a % b;  
        a = temp;  
    }  
    return a;  
}  

int main() {  
    int num1, num2;  
    printf("请输入两个整数：");  
    scanf("%d %d", &num1, &num2);  
    printf("最大公约数是：%dn", gcd(num1, num2));  
    return 0;  
}

二、利用公式求最小公倍数

最小公倍数（LCM）可以通过最大公约数来计算。两个数的最小公倍数等于这两个数的乘积除以它们的最大公约数。

1、算法原理

先求出两个数的最大公约数GCD；
用两个数的乘积除以GCD，得到最小公倍数LCM。

2、代码实现

#include <stdio.h>

// 求最大公约数的函数  
int gcd(int a, int b) {  
    while (b != 0) {  
        int temp = b;  
        b = a % b;  
        a = temp;  
    }  
    return a;  
}  

// 求最小公倍数的函数  
int lcm(int a, int b) {  
    return (a * b) / gcd(a, b);  
}  

int main() {  
    int num1, num2;  
    printf("请输入两个整数：");  
    scanf("%d %d", &num1, &num2);  
    printf("最小公倍数是：%dn", lcm(num1, num2));  
    return 0;  
}

三、用循环和条件语句实现

除了使用数学算法，还可以通过循环和条件语句来求公约数和公倍数，虽然效率较低，但理解简单。

1、求最大公约数

通过遍历从1到两个数中的较小者，找出所有能同时整除这两个数的数，最大的那个即为最大公约数。

2、求最小公倍数

从两个数中的较大者开始遍历，找到第一个能被两个数同时整除的数即为最小公倍数。

3、代码实现

#include <stdio.h>

// 求最大公约数的函数  
int gcd_by_loop(int a, int b) {  
    int gcd = 1;  
    int min = a < b ? a : b;  
    for (int i = 1; i <= min; i++) {  
        if (a % i == 0 && b % i == 0) {  
            gcd = i;  
        }  
    }  
    return gcd;  
}  

// 求最小公倍数的函数  
int lcm_by_loop(int a, int b) {  
    int max = a > b ? a : b;  
    while (1) {  
        if (max % a == 0 && max % b == 0) {  
            return max;  
        }  
        max++;  
    }  
}  

int main() {  
    int num1, num2;  
    printf("请输入两个整数：");  
    scanf("%d %d", &num1, &num2);  
    printf("最大公约数是：%dn", gcd_by_loop(num1, num2));  
    printf("最小公倍数是：%dn", lcm_by_loop(num1, num2));  
    return 0;  
}