题解 | #求最小公倍数#

求最小公倍数

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开始 '''

nn = [int(i) for i in raw_input().split()]

a = nn[0]

b = nn[1]

min_i = min(a, b)

max_i = max(a, b)

if max_i % min_i == 0:

print max_i

exit()

cycle = int(max_i / min_i) + 1

while True:

if (min_i * cycle) % max_i == 0:

print min_i * cycle

break

else:

cycle += 1

全部评论

相关推荐

不愿透露姓名的神秘牛友
11-21 19:05
面试官_我太想进步了:混学生会的,难怪简历这么水
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 10:48
点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务