在Python中，找到一系列数字中最小的相等可除的，puzz

Question

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

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?

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

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

N=10时

1.计算从5到10的所有系数：

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

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

^{pr2}$

3.得到关键功率值的乘积

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

Answer 2

很多其他答案都提到原始代码效率低下，但它们仍然会循环使用几乎所有的数字。使用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 3

您的算法效率很低，但问题的核心是您的results字典为每个可被1-20之间的数字整除的整数累积1个值，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

注意，else子句实际上在for循环中，而不是if。从流控制上的tutorial：

Loop statements may have an else clause; it is executed when the loop terminates through exhaustion of the list (with for) or when the condition becomes false (with while), but not when the loop is terminated by a break statement.

更简洁的表述是：

^{pr2}$

它使用了一个生成器表达式，这样all可以短路并避免进行不必要的计算。在

因为这是一个难题，所以我将推荐更好的算法。在