题解 | #求最小公倍数#
求最小公倍数
http://www.nowcoder.com/practice/22948c2cad484e0291350abad86136c3
coding=utf-8
''' 原思路: 互余,从乘积,求大余。求小于,求偶数余,求奇数余 --实测15ms ''' try: nn = [int(i) for i in raw_input().split()] a = nn[0] b = nn[1]
max_ji = a * b
tmp = max_ji
last_ji = tmp
min_i = min(a, b)
max_i = max(a, b)
if max_i % min_i == 0:
print max_i
exit()
last_ji = max_ji
while True:
tmp /= max_i
if tmp % a == 0 and tmp % b == 0:
last_ji = tmp
else:
break
tmp = last_ji
while True:
tmp /= min_i
if tmp % a == 0 and tmp % b == 0:
last_ji = tmp
else:
break
tmp = last_ji
while True:
if tmp % 2 == 0:
tmp /= 2
if tmp % a == 0 and tmp % b == 0:
last_ji = tmp
else:
break
else:
break
tmp = last_ji
ss = int(last_ji ** 0.5)
for i in range(3, ss + 2, 2):
tmp = last_ji
while True:
if tmp % i == 0:
tmp /= i
if tmp % a == 0 and tmp % b == 0:
last_ji = tmp
else:
break
else:
break
print last_ji
except BaseException as e:
print e
pass
''' 分享里的思路: 思路: 有个数a,b的最小公倍数c 假设a<b,那么c肯定是a的倍数; --思路清晰,但是运行时长31ms 补充1,b % a==0,则返回b, 补充2: i从b/a开始 '''