详解最大公约数和最小公倍数

三种方法暴力试除，更相损减，辗转相除

Number1.暴力试除

把它排在num1不是因为它好用，是因为 额...我乐意啦

总体思路：假设要求a,b两个数的最大公约数，先求a,b两数的因子，因子会求吧（如果不会看这里，用for循环遍历从1到a的数，如果能被a整除，即取余为0，则这个数为a的因子。如果会请自动省略这里，蟹蟹٩('ω')و）然后同理求b的因子，找到相同的部分再从中找出最大值，不仅思路麻烦，时间复杂度还高，至于代码不贴了，诶，可不是因为我不会，是因为我懒啦。

Number2.更相损减法

直接上代码叭

#include <stdio.h>
int main()
{
  int a, b, x = 0, y = 0;
  scanf("%d%d", &a, &b);
  x = a; y = b;
  while (a != b)
  {
    if (a > b)
      a = a - b;
    else b = b - a;
  }
  printf("最大公约数%d\n最小公倍数%d", a, (x / a) * (y / a) * a);
  return 0;
}

也不废话，直接讲思路：很简单将a,b差值赋给a,b中的较小值，直到a,b相等，此时a=b=最大公约数，不过你要想问我为什么，不妨直接看《九章算术》，最大公约数得到后最小公倍数还不好求吗？对叭！

Number3.辗转相除法

代码镇帖

#include <stdio.h>
int main()
{
  int a, b, t = 0, x = 0, y = 0;
  scanf_s("%d%d", &a, &b);
  x = a; y = b;
  while (b != 0)
  {
    t = a % b;
    a = b;
    b = t;
  }
  printf("最大公约数%d\n最小公倍数%d", a, (x / a) * (y / a) * a);
  return 0;
}

思路：如果a<b,第一次循环就会直接将a,b交换位置（这也是这个算法精妙所在，完全不用考虑a,b的大小关系），然后往下循环时将a%b赋给较小值b，将b赋值给a，最后得到最大公约数a,但要注意更相损减法后a,b都是最大公约数，而辗转相除法（这个问欧几里得）后只有a是最大公约数。

两种方法本质相同但又各有优劣，从算法本身看辗转相除大大减少了运算时间，所以当遇到一个很大的数的时候，它的运行速率要远快于更相损减法，但辗转相除如果变量不初始化就会进入无限循环从而得不到结果。

但综上所述，如果要攻算法，建议用辗转相除，因为更相损减法容易运行超时啦