C语言——最大公约数与最小公倍数的秘密

part1.求两个正整数的最大公约数之辗转相除

辗转相除，也叫欧几里得算法或除法求余法，是数学上用于计算两个正整数最大公约数（Greatest Common Divisor, GCD）的一种古老而有效的方法。它的基本原理是利用辗转相除法的性质：两个正整数a和b（假设a>b），它们的最大公约数等于b和a除以b的余数c的最大公约数。如果余数为0，则b就是原两数的最大公约数；若不为0，则继续将原来较小的数b作为新的被除数，原来的余数c作为新的除数，这个过程不断重复，直到余数为0为止。这种方法体现了递归的思想。实际代码如下：

#include<stdio.h>

int main()
{
    long a = 0;
    long b = 0;

    scanf("%ld %ld", &a, &b)；
    long i = a;
    long j = b;
    long r = 0;
    while (r = i % j)
    {
        i = j;
        j = r;
       
    }//辗转相除法
    //用较大数除以较小数，再用出现的余数去除除数，再用新出现的余数去除前面的余数，
    // 反复直到最后余数是0才终止循环，且最后的除数就是这两个数的最大公约数
    printf("%ld\n", j);

    return 0;
}

part2.求两个正整数的最小公倍数与最大公约数之和

欧几里得发现的定理(a,b)*[a,b]=a*b,其中最大公约数表示为：(a，b)，最小公倍数表示为：[a，b]。

依此，我们不仅可以求最小公倍数，还可以求两个正整数的最小公倍数与最大公约数之和。

#include<stdio.h>

int main()
{
    long a = 0;
    long b = 0;

    scanf("%ld %ld", &a, &b)；
    long i = a;
    long j = b;
    long r = 0;
    while (r = i % j)
    {
        i = j;
        j = r;
       
    }
    printf("%ld\n", a * b / j + j);//求两个正整数的最小公倍数与最大公约数之和
    //i = a * b / j//这个是求两个正整数的最小公倍数

    return 0;
}

part3.求最小公倍数的另一种方法

优点：代码简洁；不足：运行时间比前面代码长

#include<stdio.h>
int main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d", &a, &b);
	int i = 1;
	while ((a * i) % b)
	{
		i++;
	}
	printf("%d\n", a * i);
	return 0;
}

代码解读：a*i是a的i倍，当a*i%b==0时，a*i也是b的k倍。依此方法可以试出a和b的最小公倍数。

注：本文并非完全原创，借鉴了很多大佬的思维与方法，望周知