最大公约数与最小公倍数

前言：

   最大公约数（最大公因数）是指两个或多个整数共有约数中最大的一个。最小公倍数是指两个或多个整数的公倍数里最小的那一个。最大公约数记为（a，b），最小公倍数是已知几个数的公倍数，且是最小的那一个。

1.法一：辗转相除法 

#include<stdio.h>
int main ()
{
    int a,b; 
    int r = 0;
    int l = 0;//初始化 
    scanf("%d %d",&a,&b);
    l =a*b;//由定理可知 ,提前存下两数乘积 
    //辗转相除 
    do
    {
    	r=a%b;
    	a=b;
    	b=r;
	}while(b); 
    printf("最大公约数为：%d\n",a);
    printf("最小公倍数为：%d\n",l/a);
    return 0;
}

下面我来逐步讲解 辗转相除法。

  首先我们要知道，公约数是两数共同的因子，比如2是4和6的因子，12是36和48的因子。最大公约数就是两数最大的因子。知道了这点，结合公式就很容易求出来了，许多初学者忘记概念才觉得很难懂。

  辗转相除法的基本原理可描述如下：若b是0，则最大公约数是a中的值；否则计算a除以b的余数r，把b保存到a中，并把余数r保存到b中，重复上述过程，直到b为0，a中的数即为最大公约数。

   使用循环结构，根据步骤依次写入循环，当b为0时退出循环。

需要注意的点就是：两个自然数的最大公约数与它们的最小公倍数的乘积等于这两个数的乘积。

之所以我们需要提前保存两数乘积，是因为经过循环后，a、b的值被改变。

2.法二：穷举法（暴力法）

#include <stdio.h>

int gcd(int a, int b) {
    int max_gcd = 1;
    for (int i = 1; i <= a && i <= b; i++) 
	{
        if (a % i == 0 && b % i == 0) {
            max_gcd = i;//越往后i越大，所以不用比较 
        }
    }
    return max_gcd;
}

int main() {
    int num1, num2;
    printf("输入两数: ");
    scanf("%d %d", &num1, &num2);
    printf("最大公约数为： %d\n", gcd(num1, num2));
    return 0;
}

使用循环结构依次判断，效率较辗转相除法慢，适用于小整数。

3.法三：递归的更相减损法

递归是一种编程技巧，它允许一个函数直接或间接地调用自己。在求解最大公约数的问题中，递归方法的核心思想是将问题分解为更小的子问题。

更相减损术是一种古老的算法，用于计算两个正整数的最大公约数。其原理是重复从较大的数中减去较小的数，直到其中一个数变为零。当其中一个数变为零时，另一个数即为最大公约数。（辗转法中也有类似思想）

递归实现的更相减损术如下：

#include <stdio.h>
int gcd(int a, int b) {
    if (b == 0) 
	{
        return a;
    } 
	else 
	{
        return gcd(b, a % b);
    }
}

int main() 
{
    int num1, num2;
    printf("输入两数 ");
    scanf("%d %d", &num1, &num2);
    printf("最大公约数为： %d\n", gcd(num1, num2));
    return 0;
}

在这个递归函数中，如果 b 等于零，函数就返回 a，因为任何数和零的最大公约数都是它本身。如果 b 不等于零，函数就递归调用自己，这次的参数是 b 和 a % b。

4.法四：Stein算法（二进制GCD）

这个方法是网络归纳的，提供了不同的视角和方法，可供大家思考。

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    int k;
    for (k = 0; ((a | b) & 1) == 0; k++) {
        a >>= 1;
        b >>= 1;
    }
    while ((a & 1) == 0)
        a >>= 1;
    do {
        while ((b & 1) == 0)
            b >>= 1;
        if (a > b) {
            int temp = a;
            a = b;
            b = temp;
        }
        b = b - a;
    } while (b != 0);
    return a << k;
}

int main() {
    int num1, num2;
    printf("Enter two numbers: ");
    scanf("%d %d", &num1, &num2);
    printf("The GCD of %d and %d is %d\n", num1, num2, gcd(num1, num2));
    return 0;
}