c语言经典习题之最大公约数和最小公倍数

c语言经典习题之最大公约数和最小公倍数

这篇文章我们最大公约数和最小公倍数

目录

最大公约数

方法一：

方法二：

最小公倍数

方法一：

方法二：

方法三：

---

最大公约数

最大公约数指两个或多个整数共有约数中最大的一个

题目：求两个数中的最大公约数

方法一：

思路：我们可以从两个数中小的数开始，只要这个数能同时整除这两个数就是最大公约数，否则的话就-1试除。

  #include
  int main()
  {
      long long m=0;
      long long n=0;
      scanf("%lld %lld",&m,&n);
      long long max = m>n?n:m;//最大公约数
      long long ret =0;
      while(1)//求最大公约数
      {
          if(m%max==0&&n%max==0)
          {
              break;
          }
          max--;
      }
      printf("%lld",max);
      return 0;
  }

方法二：

辗转相除法

#include
int main()
{
    long long n = 0;
    long long m = 0;
    scanf("%lld %lld", &n, &m);
    long long n1 = n;
    long long m1 = m;
    long long ret = 0;
    while (ret = n % m)
    {
        n = m;
        m = ret;
    }
    //m就是最大公约数
    printf("%lld",m);
    return 0;
}

最小公倍数 方法一：

思路：我们可以从两个数中大的数开始，只要这个数能同时整除这两个数就是最小公倍数，否则的话就+1试除。

#include
int main()
{
    long long m=0;
    long long n=0;
    scanf("%lld %lld",&m,&n);
    long long min = m>n?m:n;//最小公倍数
    long long ret =0;
    while(1)//求最小公倍数
    {
        if(min%m==0&&min%n==0)
        {
            break;
        }
        min++;
    }
    printf("%lld",min);
    return 0;
}

方法二：

利用最大公约数与最小公倍数的关系来求得最小公倍数

#include
int main()
{
    long long n = 0;
    long long m = 0;
    scanf("%lld %lld", &n, &m);
    long long n1 = n;
    long long m1 = m;
    long long ret = 0;
    while (ret = n % m)
    {
        n = m;
        m = ret;
    }
    //m就是最大公约数
    printf("%lld", ((m1 * n1) / m));//最小公倍数。
    return 0;
}

方法三：

我们利用乘法来解决，首先最小公倍数一定都能整除给出的两个数，又a*b=公倍数，我们可以这样理解如果a最先乘以一个数能够整除b的话那a*那个数就是我们的最小公倍数。

#include
int main()
{
    int n = 0;
    int m = 0;
    scanf("%d %d", &m, &n);
    int i = 0;
    while (i * m != n)
    {
        i++;
    }
    printf("%d", i * m);
    return 0;
}