python - Project Euler 在 python 中获得最小倍数

Question

我在做欧拉计划中的第五​​题:“2520 是能被 1 到 10 中的每一个数整除而没有余数的最小数。”

能被 1 到 20 的所有数字整除的最小正数是多少？”

我构建了以下代码，当使用 1 - 10 作为除数时，它找到了正确的值 2520，但当使用 1 - 20 时，代码似乎永远持续下去。同样，我不希望代码只是我出错的地方的一两个指针。谢谢

def smallestDiv(n):
    end=False
    while end == False:
        divisors = [x for x in range(1,21)]    # get divisors
        allDivisions = zip(n % i for i in divisors)    # get values for  n % all integers in divisors
        check = all(item[0]  == 0 for item in allDivisions )   # check if all values of n % i are equal to zero
        if check:         # if all values are equal to zero return n
            end = True
            return n
        else:             # else increase n by 1
            n +=1

编辑:

我使用了一些我找到的与 LCM 相关的代码，并使用 reduce 来解决问题:

def lcm(*values):
    values = [value for value in values]
    if values:
        n  = max(values)
        m = n
        values.remove(n)
        while any( n % value for value in values ):
            n +=m
        return n
    return 0

print reduce(lcm, range(1,21))

Answer 1

如果问题很难，尝试解决一个更简单的版本。在这里，如何计算两个 数的最小公倍数。如果您阅读过任何数论书籍(或考虑过质因数)，则可以使用最大公约数函数(由欧几里德算法实现)来做到这一点。

from fractions import gcd
def lcm(a,b):
    "Calculate the lowest common multiple of two integers a and b"
    return a*b//gcd(a,b)

观察 lcm(a,b,c) ≡ lcm(lcm(a,b),c) 用 Python 的 reduce 很容易解决你的问题功能

>>> from functools import reduce
>>> reduce(lcm, range(1,10+1))
2520
>>> reduce(lcm, range(1,20+1))
232792560