最大公约数和最小公倍数的优化

Question

题目是这样的，想问一下各位友友还能怎么优化，让它变快

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int Pan(int min,int p,int q)
{
    int m = p < q ? p : q;
    for(m=m;m>=min;m--)
    {
        if (p % m == 0 && q % m == 0)
        {
            if (m == min)
                return 1;
            else
                return 0;
        }
    }
    return 0;
}
int main()
{
    int x = 0, y = 0;
    scanf("%d%d", &x, &y); int count = 0; int mix = x * y;
    int max = x > y ? x : y; int p = 0, q = 0; int min = mix / max;
    for (p = min;p<=max/2 ; p++)
    {
        for (q=p;q<=max;q++)
        {
            if (Pan(min, p, q) == 1)
            {
                if ((p * q) / min == max)
                    count++;
            }
        }
    }
    printf("%d", count*2);
    return 0;
}

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7519474
• 这篇博客也不错, 你可以看下写两个函数，分别求两个整数的最大公约数和最小公倍数，用主函数调用这两个函数，并输出结果。
• 您还可以看一下 周昊老师的小白学习课程：梯度下降算法与公式详细推导课程中的 从一个线性回归模型案例谈起小节, 巩固相关知识点
  
• 以下回答来自chatgpt:

  首先，需要明确最大公约数和最小公倍数的定义和计算方法。

  最大公约数（GCD）是指两个或多个整数共有约数中最大的一个数。求两个数的最大公约数可以使用辗转相除法，即一直用两个数的较小数去除较大数，直到余数为0，此时的除数就是最大公约数。

  最小公倍数（LCM）是指可同时被两个或多个整数整除的最小正整数。求两个数的最小公倍数可以利用最大公约数的性质，即最小公倍数等于两个数的乘积除以最大公约数。

  优化方法： 1. 在计算最大公约数时，可以使用更高效的算法，如欧几里得算法（辗转相除法）。可以将参考资料中的gcd方法进行调用。

  def gcd(a, b):
      while b != 0:
          temp = a % b
          a = b
          b = temp
      return a
  

  1. 在计算最小公倍数时，可以直接利用最大公约数的结果，将两个数的乘积除以最大公约数得到最小公倍数。

  def lcm(a, b):
      return a * b // gcd(a, b)
  

  1. 如果需要计算多个数的最大公约数和最小公倍数，可以先求出前两个数的最大公约数，然后再将最大公约数和下一个数求最大公约数，依次类推，直到最后一个数。这样可以减少计算的次数。

  代码示例：

  def gcd(a, b):
      while b != 0:
          temp = a % b
          a = b
          b = temp
      return a
  
  def lcm(a, b):
      return a * b // gcd(a, b)
  
  def calculate_gcd_and_lcm(numbers):
      gcd_result = gcd(numbers[0], numbers[1])
      lcm_result = lcm(numbers[0], numbers[1])
  
      for i in range(2, len(numbers)):
          gcd_result = gcd(gcd_result, numbers[i])
          lcm_result = lcm(lcm_result, numbers[i])
  
      return gcd_result, lcm_result
  
  numbers = [12, 18, 24]
  gcd_result, lcm_result = calculate_gcd_and_lcm(numbers)
  
  print("最大公约数:", gcd_result)
  print("最小公倍数:", lcm_result)
  

  输出结果： 最大公约数: 6 最小公倍数: 72

  通过以上优化方法，可以提高最大公约数和最小公倍数的计算速度。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^