python之逆解最大公约数与最小公倍数

2024-03-04 13:06| 来源: 网络整理| 查看: 265

1.贴题

题目来自PythonTip 逆解最大公约数与最小公倍数

我们经常遇到的问题是给你两个数，要你求最大公约数和最小公倍数。今天我们反其道而行之，给你两个数a和b，计算出它们分别是哪两个数的最大公约数和最小公倍数。输出这两个数，小的在前，大的在后，以空格隔开。若有多组解，输出它们之和最小的那组。注：所给数据都有解，不用考虑无解的情况。

例如：a=3, b = 60

则输出：12 15

2.说明

一开始想要暴力破解，后来发现暴力破解也不是很简单，所以就投机取巧想着利用现成的函数。

3.参考代码

python3版本

import math #导入math库以便使用最大公约数函数gcd c = min(a,b) #取ab中小的数即为最大公约数 d = max(a,b) #取ab中大的数即为最小公倍数 flag = False #预先将flag置为False for i in range(c,d+1): #外层循环i for j in range(c,d+1): #内层循环j if math.gcd(i,j) == c and i*j/c==d and j%i != 0: #如果ij的最大公约数为c且最小公倍数为d且ij互质 print(i,j) #则说明找到了将其打印 flag = True #将flag置为True break #跳出内层循环 if flag: #检验flag，假继续循环，真跳出外层循环 break

python2版本

from fractions import gcd c = min(a,b) d = max(a,b) flag = False for i in range(c,d+1): for j in range(c,d+1): if gcd(i,j) == c and i*j/c==d and j%i != 0: print i,j flag = True break if flag: break 4.优化代码

虽然上面的代码通过了平台的测试，但是看了人家的代码之后发现上面的代码还是有问题的。因此结合人家的思路修改优化了代码。

import math c = min(a,b) d = max(a,b) l = [] #增加一个列表l用于存放所有满足条件的数组 for i in range(c,d+1): for j in range(c,d+1): if math.gcd(i,j) == c and i*j/c==d: #删去互质条件因为两数不需要互质 l.append((i,j)) #如果满足条件，将两数打包为tuple添加到l列表 l.sort(key = lambda x:x[0]+x[1]) #使用两数之和作为key对l中的元素进行排序，默认为升序因此排序后第一组数据为所求的 print(" ".join(map(str,l[0]))) #将第一组数据以空格连接输出 5.其他写法

聚焦不同因数项法来自blueauris（python2写法）

import math def gcd(p,q): p,q = (p,q) if (p > q) else(q,p) while(p%q!=0): p,q = q,p%q return q a,b = (a,b) if a

【本文地址】

公司简介

联系我们