小练习结果揭晓：找出最小的能被1-20中每个数整除的数

冬雪雪冬

原帖子：http://bbs.fishc.com/thread-70160-1-1.html


题目：
2520 是最小的能被 1-10 中每个数字整除的正整数。

最小的能被 1-20 中每个数整除的正整数是多少？


本次题目比较简单，大家的思路也相近，所以就不考虑运行时间的差别了。
一种思路是计算出这20个数字的最小公倍数，先算出二个数的最小公倍数，再逐一计算得到20个数字的。为得到最小公倍数先用辗转相除法得到最大公约数，则最小公倍数=两数的乘积除以最大公约数。
这里有两个小技巧：
1.能被20整除必然能被1，2，4，5，10整除，以此类推需要计算的数字只剩下11~20了，既然有12和15那么20也可以去掉了。
2.很多答案的辗转相除法都利用了中间变量，其实python是可以简化掉的。
我写的程序如下：

1. from functools import reduce
   
2. 
   
3. def gcd(x, y):
   
4.     while y != 0:
   
5.         x , y = y, x % y
   
6.     return x
   
7. 
   
8. def lcm(x, y):
   
9.     return x * y // gcd(x, y)
   
10. 
    
11. print(reduce(lcm, range(11, 20)))

复制代码

另一种方法是把11~20中的任意两个或两个以上数字的公因子提出来，再把所有的数字相乘，这个更符合人计算的思维方式。

1. from functools import reduce
   
2. 
   
3. list1 = [11, 12, 13, 14, 15, 16, 17, 18, 19,]
   
4. list2 = [2, 3, 5, 7]
   
5. list3 = []
   
6. for i in list2:
   
7.     while True:
   
8.         s = False
   
9.         for j in range(len(list1)):
   
10.             if list1[j] % i == 0:
    
11.                 list1[j] = list1[j] // i
    
12.                 s = True
    
13.         if s == True:
    
14.             list3.append(i)
    
15.         else:
    
16.             break
    
17.          
    
18. list3 = list1 + list3
    
19. print(reduce(lambda x, y: x* y, list3))

复制代码

最后的答案是：
232792560
本次给出正确答案的鱼油是：DingRan， 旺仔sama， 星宇的雨， holdme， zooo， 小剑剑， 挥舞乾坤， lingtingliushe，Hewee，落叶飞空，老忘， 小火木， ajforfun，wangzhenas， 不爱穿内裤，wujtao

zooo

支持ING~

wangzhenas

小小小丝

poiulp

来学习了！

zxc123qwe

支持

zxc123qwe

支持

wangguohui

来学习下

lifeidao

持续关注