原题链接：[编程入门]最大公约数与最小公倍数
解题思路:
“求最大公因数和最小公倍数”这个问题相信大家都已经学过了，就是利用短除法分解质因数。这对于我们人来说非常简便，但机器可以死算（相当于枚举算法），所以我们可以用枚举算法。最简单的也就是这么写：
参考代码:
| a, b = map(int, input().split()) s = 1 n = 1 if a % i == 0 and b % i == 0: s = i if a > b: n = a * 2while n % b != 0: n += a else: n = b * 2while n % a != 0: n += b print(s, n) |
但如果你输入“600000000000000 300000000000000000”会怎么样呢？
此程序一定会执行很久。我们人一下子就能看出来最大公因数是600000000000000，最小公倍数是300000000000000000。但此程序不能一下子判断出来。所以我们可以让程序执行的速度更快些。
参考代码:
| a, b = map(int, input().split()) s = 1 n = 1 if a % b == 0: print(b, a) elif b % a == 0: print(a, b) else: if a > b: for i in range(2, b): if a % i == 0 and b % i == 0: s = i n = a * 2 while n % b != 0: n += a print(s, n) else: for i in range(2, a): if a % i == 0 and b % i == 0: s = i n = b * 2 while n % a != 0: n += b print(s, n) |
我门都知道相邻的两个自然数（0除外）都互质，相邻的两个自然数都相差1，他们的公因数只有1，最小公倍数就是他们相乘。
如果你输入“600000000000000 599999999999999”会怎么样呢？
此程序也一定会执行很久。所以我们还可以让程序执行的速度更快些。
参考代码:
| a, b = map(int, input().split()) s = 1 n = 1 if a % b == 0: print(b, a) elif b % a == 0: print(a, b) elif a - b == 1 or b - a == 1: print(s, a * b) else: if a > b: for i in range(2, b // 2 + 1): if a % i == 0 and b % i == 0: s = i n = a * 2 while n % b != 0: n += a print(s, n) else: for i in range(2, a // 2 + 1): if a % i == 0 and b % i == 0: s = i n = b * 2 while n % a != 0: n += b print(s, n) |
程序不能光看结果，还要看效率，不然就不实用。准确率高、效率高，这样的程序才“像样”。
0.0分
3 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复