最大公约数和最小公倍数的优化
题目是这样的，想问一下各位友友还能怎么优化，让它变快
#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;
}
- 帮你找了个相似的问题, 你可以看下: 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- 在计算最小公倍数时，可以直接利用最大公约数的结果，将两个数的乘积除以最大公约数得到最小公倍数。
def lcm(a, b): return a * b // gcd(a, b)- 如果需要计算多个数的最大公约数和最小公倍数，可以先求出前两个数的最大公约数，然后再将最大公约数和下一个数求最大公约数，依次类推，直到最后一个数。这样可以减少计算的次数。
代码示例：
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
通过以上优化方法，可以提高最大公约数和最小公倍数的计算速度。
如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^
可以google下，辗转相除法，循环几次即可得到