论坛 › C\C++交流 › 求问! 这样子求最大公因数和最小公倍数可以吗？

1522843196 发表于 2020-5-21 16:37:00

求问! 这样子求最大公因数和最小公倍数可以吗？

#include <stdio.h>

int main()
{
        long long int m, n, k, gcd;
        int t;
        scanf("%lld %lld", &m, &n);
       
        if(m < n)
        {
                t = m;
                m = n;
                n = t;
        }
        for(k = 2; k < n; k++)
        {
                if(m % k == 0 && n % k == 0)
                {
                        gcd = k;//最大公因数
                }
        }
       
        printf("%lld\n%lld\n", gcd, ((m*n)/gcd));//(m*n)/gcd最小公倍数
       
        return 0;
}

永恒的蓝色梦想 发表于 2020-5-21 16:50:14

不行，可能导致gcd根本没初始化，应该改成：#include <stdio.h>

int main()
{
    long long int m, n, k, t, gcd = 1;
    scanf_s("%lld %lld", &m, &n);

    if (m < n)
    {
      t = m;
      m = n;
      n = t;
    }
    for (k = 2; k < n; k++)
    {
      if (m % k == 0 && n % k == 0)
      {
            gcd = k;//最大公因数
      }
    }

    printf("%lld\n%lld\n", gcd, ((m * n) / gcd));//(m*n)/gcd最小公倍数

    return 0;
}

而且你的代码效率不行，给你个快的，欧几里得法：#include<stdio.h>
typedef long long ll;


ll gcd(ll a, ll b)
{
    ll t;
    while (b) {
      t = a % b;
      a = b;
      b = t;
    }
    return a;
}


int main()
{
    ll a, b, t;
    scanf("%lld%lld", &a, &b);
    t = gcd(a, b);
    printf("%lld\n%lld\n", t, a * b / t);
    return 0;
}

查看完整版本: 求问! 这样子求最大公因数和最小公倍数可以吗？