解题思路:
“求最大公因数和最小公倍数”这个问题相信大家都已经学过了,就是利用短除法分解质因数。这对于我们人来说非常简便,但机器可以死算(相当于枚举算法),所以我们可以用枚举算法。最简单的也就是这么写:
参考代码:
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 人评分
printf基础练习2 (C语言代码)浏览:741 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:523 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:513 |
【简单计算】 (C语言代码)浏览:622 |
IP判断 (C语言描述,蓝桥杯)浏览:1095 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:560 |
1014题解浏览:485 |
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:1479 |
排序算法(选择,插入,冒泡)浏览:775 |
A+B for Input-Output Practice (IV) (C语言代码)浏览:506 |