题目
Smallest multiple
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all
of the numbers from 1 to 20？
最小公倍数
2520是最小的能够被1到10整除的数。
最小的能够被1到20整除的正数是多少？
解法一
暴力循环解题
依次加1，
用这个方法解决1-10还是可以的，解决1-20就太浪费时间了，至少要跑10分钟
n = 20 sn = n while True: for i in range(1,n+1): if sn%i == 0: pass else: sn+=1 break else: break if sn%10000==0: print(sn) print(sn)
解法二
利用质数求解
其实题目就是想让求1-20 的最小公倍数，
而质数的公倍数就是质数相乘
例：2，3，5的公倍数 就是2 * 3 * 5 = 30
我们可以利用这个性质先求出来所有质数的公倍数 skip 、
又因为最后的结果，也要是质数的倍数，所以，结果也是skip的倍数
我们以skip为步长，依次判断
经过最后的测试，时间仅需要：0.000997304916381836
n = 20 # 1-n skip = 1 for i in range(1,n+1): # 求里面的质数的乘积，因为质数互质， if fs(i): skip *= i # 最后求出的数一定是skip的倍数，只有是skip的倍数，才能满足所有的质数为它的因子 bei = 1 while True: skip2 = bei*skip # 求倍数 for i in range(1,n+1): if skip2%i!=0: # 如果不满足1-n为它的因数，就增加一倍 bei+=1 break else: # for else 结构自己在看看，当1-n所有的数都是 skip2 的因数，跳出while循环 break print(skip2)
