我正在尝试解决下文详述的 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 个目标。谢谢
最佳答案
您的算法效率很低,但问题的核心是您的 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.
更简洁的表达方式是:
candidate = 0
while not success:
candidate += 1
success = all((candidate % divisor == 0 for divisor in divisors))
它使用生成器表达式,因此 all
可以短路并避免进行不必要的计算。
由于这是一个谜题,我将继续推荐更好的算法。
关于python - 在 Python 中找到一个数字范围内最小的可整除数,谜题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17980184/