python - 优化代码以找到可被 1-20 之间的所有整数整除的最小数

Question

我目前正在尝试解决问题“可以被 1 到 20 的所有数字整除的最小正数是多少？”

到目前为止，我已经编写了一些似乎可行的代码，但需要很长时间。此外，我不得不在 if 中使用大量的“和”语句，这看起来既不高效也不专业。

我能做些什么来优化这段代码并让它更整洁？

number = 1
result = 0

def divide(candidate):
    if candidate % 2 == 0 and candidate % 3 == 0 and candidate % 4 == 0 and candidate % 5 == 0 and candidate % 6 == 0 and candidate % 7 == 0 and candidate % 8 == 0 and candidate % 9 == 0 and candidate % 10 == 0 and candidate % 11 == 0 and candidate % 12 == 0 and candidate % 13 == 0 and candidate % 14 == 0 and candidate % 15 == 0 and candidate % 16 == 0 and candidate % 17 == 0 and candidate % 18 == 0 and candidate % 19 == 0 and candidate % 20 == 0:
        global result
        result = 1
        return 1

    else:
       global number
        result = 0
        number = number + 1
        return 0

while result == 0:
divide(number)

print "The lowest number divisible by all integers between 1-20 is:", number

澄清一下，这不是家庭作业，我正在自学 Python，并且正在尝试一些 ProjectEuler 问题作为其中的一部分。

score 9 · Accepted Answer

您的问题可以在没有计算机帮助的情况下轻松解决，因此优化版本将简单地打印答案。很难说出您认为可以接受的优化量。

以下是如何在没有计算机的情况下解决这个问题。能被 1 到 20 的所有数整除的最小数必须能被这些数中出现的所有素数整除。另一方面，如果我们有一个数可以被这个范围内的所有素数整除，那么它将可以被从 1 到 20 的所有数整除。由于具有不同基数的素数是互质的，因此所有最高素数的乘积这个范围内的每个素数都是答案。所以这里是优化的代码：

print 2**4 * 3**2 * 5 * 7 * 11 * 13 * 17 * 19

score 2 · Accepted Answer

您可以从消除作为先前数字的因素的数字开始。所有能被 4 整除的数字都能被 2 整除。所有能被 10 整除的数字都能被 5 整除，所有能被 9 整除的数字都能被 3 整除，以此类推。

score 0 · Accepted Answer

这里一个非常简单但非常有效的方法是仅使用素数及其幂。为什么你必须考虑他们的乘数，对吧？将您的“和”条件减少到只有 4,9,16,5,7,11,13,17,19

score 0 · Accepted Answer

如果是我，我会尝试“修改”（％）素数。我不会使用从 1 到 20 的每个数字。

python - 优化代码以找到可被 1-20 之间的所有整数整除的最小数

4 回答 4

Related

Reference