在Python中找到一系列数字中最小的等分数，谜题

Question

我正在尝试解决下面详述的一个projecteuler难题。我当前的函数适用于数字1到10，但当我尝试1到20时，它只会永远循环而没有结果。

2520是可以被1到10的每个数字除的最小数，没有任何余数。可以被1到20的所有数字整除的最小正数是多少？

def calculate():
    results = dict()
    target = 20
    num_to_test = 1
    while len(results) < target:
        for j in range(1, target+1):
            results[num_to_test] = True
            if num_to_test % j != 0:
                # current num_to_test failed in the 1-10, move on
                del results[num_to_test]
                break

        num_to_test += 1
    return min(results)

有人能看到逻辑上的任何问题吗？特别是我想知道为什么它能实现10个目标，而不是20个。谢谢

Answer 1

许多其他答案提到原始代码效率低下，但它们仍然循环遍历几乎每个数字。利用lcm功能不是更有效吗？

def calculate(num, current_lcm = 1):
    if (num == 1): return current_lcm
    return calculate(num - 1, lcm(num, current_lcm))

def lcm(a, b):
    return a * b // gcd(a, b)

def gcd(a, b):
    while b:      
        a, b = b, a % b
    return a

print calculate(20)

Answer 2

实际上，我有非常有效的算法来解决这个问题。我不会给你密码，但我可以给你指路

对于N=10

1、计算从5到10的所有数字的所有因子：

 [[2, 3], [7], [2, 2, 2], [3, 3], [2, 5]]

2.计算列表中每个素数的最大数

 {2: 3, 3: 2, 5: 1, 7: 1}

关键功率值的3.get产品

 2^3 * 3^2 * 5 * 7 = 2520

Answer 3

你的算法效率很低，但问题的核心是，你的结果字典为每个整数累加一个值，该值可以被1-20的数字整除，而你的while循环试图继续运行，直到它有20个这样的数字。

这是实现这种低效算法的一种正确方法：

def calculate():
    target = 20
    candidate = 1
    success = False
    divisors = range(1, target+1)
    while not success:
        for divisor in divisors:
            if candidate % divisor != 0:
                candidate += 1
                break
        else:
            success = True

    return candidate

请注意，etc子句确实在for循环上，而不是if。来自流控制教程：

循环语句可以有else子句；当循环通过耗尽列表终止（使用for）或当条件变为false（使用while）时执行，但当循环通过break语句终止时不执行。

更简洁的表达方式是：

candidate = 0
while not success:
    candidate += 1
    success = all((candidate % divisor == 0 for divisor in divisors))

它使用生成器表达式，因此所有都可以短路，并避免进行不必要的计算。

由于这是一个谜，我将继续建议更好的算法。