优化eulerproject解决方案5-最小倍数

Question

如何优化我的代码？我花了大约3分钟才终于得到了答案。

这是m码：

def myfunc():
    smallest = 0;
    while True:
        smallest +=1
        for x in range(1, 21):
            if smallest % x != 0:
                break
            else:
                if x == 20:
                    print(smallest)
                    return
myfunc()

谢谢:)

Answer 1

您可以简单地生成从1到(包括) 20之间的所有元素中最不常见的倍数。

三个(或更多个) lmc(a,b,c) == lmc(lmc(a,b),c)的最小公共倍数(lcm)。

现在，为了计算最小公共倍数，我们可以使用欧几里德算法计算最大公因子(gcd)：

def gcd(x,y):
    while y != 0:
        x, y = y, x % y
    return x

所以现在我们可以用lcm来定义gcd了

def lcm(x,y):
    return x*y//gcd(x,y)

然后让它成为一个清单：

def lcm_list(x,*args):
    for y in args:
        x = lcm(x,y)
    return x

所以现在我们可以像：

lcm_list(*range(1,21))

这就产生了：

>>> lcm_list(*range(1,21))
232792560

它可以除以从1到20的每一个数字：

>>> [232792560%i for i in range(1,21)]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Answer 2

这个问题可以解析地解决。不需要编程。

逻辑如下:如果n除以一个数字k，那么它也会对k * m进行划分。因此，我们正在寻找的数字是所有数字n的乘积，它不能写成集合中任何较小数字的乘积。

这些数字都不可能是非素数幂复合数，否则它是集合中较小数的乘积，但另一方面，它必须包含小于20的所有素数幂，因为它们不是集合中任何较小数的乘积。由于我们知道素数(记住，或者参考某个列表/写函数)，我们现在有了一个解决方案。

因此我的代码是

>>> (2 ** 4) * (3 ** 2) * 5 * 7 * 11 * 13 * 17 * 19
232792560