牛客题目-用短除法和欧几米德算法求两个数的最小公倍数 最大公约数

题目描述

正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。

解题思路:

1 短除法

import sys def min_common_num(num1, num2): """使用短除法 找出所有的公约数存放于 列表 gong_yue_shu 将每次进行公约数计算后的结果保存到列表 chu_shu 最后将两个列表中的所有元素相乘即为最小公倍数 注意：此题方法 可以 拓展 任意多个数的 最小公倍数 和 最大公约数 """ if(num1==num2): # 避免两个数都是1的情况 return num1 flag = 1 gong_yue_shu = [] chu_shu = [num1, num2] while flag: for i in range(2, min(chu_shu[0], chu_shu[1])+1): if (chu_shu[0] % i == 0 and chu_shu[1] % i == 0): gong_yue_shu.append(i) chu_shu = [chu_shu[0] /i, chu_shu[1] /i] continue else: flag = 0 gongyueshu_chushu = gong_yue_shu + chu_shu gongbeishu = 1 for t in gongyueshu_chushu: gongbeishu *= t #print(gongbeishu) print(int(gongbeishu)) for line in sys.stdin: a = line.split() min_common_num(int(a[0]), int(a[1]))

2 欧几米德算法

最大公约数gcd解法如下：

def gcd(a, b): if b == 0: return a return gcd(b, a%b)

最小公倍数：

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