1. 求最大公约数

1.1第一种方法暴力求解

这种方法是最容易想到的，下面看一下思路，比如说找16 18 最大公约数

取到两个数，先判断大小，将小的拿出来。然后用小的这两个数进行取模运算。如果不是对这个取出来的数“–”

1.2 第二种方法辗转相除法

这种方法也是最不容易想到的，但却是比暴力求解更有效率的一种方法，下面看一下原理

不用对两个数判断大小，直接取模，如果不为零执行while中的语句，将m赋值给n，然后将取模后的数字，赋值给m，这样循环下来，当模为零时跳出来，max就是最大公约数

1.3 第三种方法相减法

最大公约数还有这样一种性质

所以我们可以根据这个性质来，求最大公约数


#include <stdio.h>

int main()
{
    int a = 0;
    int b = 0;
    scanf("%d%d",&a,&b);
    while(a!=b)
    {
        if(a>b)
        a = a - b;
        if(a<b)
        b = b - a;
    }
    printf("%d\n",a);
    return 0;
}

2.求最小公倍数

2.1 第一种方法暴力求解

和前面的求最大公约数方法基本一样

2.2 第二种方法在最大公约数的基础上求

3.看一个牛客网上的练习题

链接小乐乐与欧几里得_牛客题霸_牛客网 (nowcoder.com)

我们直接用辗转相除法来做

 int main()
 {
     long long n, m;
     long long max = 0, min = 0, tmp = 0;
     scanf("%lld %lld\n", &n, &m);
     //最大公约数
     long long a = n, b = m;
     while (tmp = n % m)
     {
         n = m;
         m = tmp;
     }
     max = m;
     //最小公倍数
     min = a * b / max;
     printf("%lld\n", min + max);
     return 0;
 }

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/87387.html