python - 了解 Python 中 Euler 项目的解决方案

Question

我目前正在研究 Euler 项目。我已经开始使用 JavaScript，昨天我已经切换到 Python，因为我遇到了一个问题，这个问题用 Javascript 解决起来似乎很复杂，但用 Python 很容易解决，所以我决定再次从第一个问题开始 python 。

我在第 5 题中要求我找到能被 1 到 20 之间的所有数字整除的最小正数。

我知道如何用纸和铅笔解决它，并且我已经使用编程解决了它，但是为了优化它，我在 Euler 项目的论坛上找到了这个解决方案。

它看起来很优雅，而且速度相当快，与我的相比快得离谱，因为解决数字 1 到 1000 的相同问题大约需要 2 秒，而我的需要几分钟。

我试图理解它，但我仍然难以理解它到底在做什么。在这里:

i = 1
for k in (range(1, 21)):
    if i % k > 0:
        for j in range(1, 21):
            if (i*j) % k == 0:
                i *= j
                break
print i

它最初是由一个名为 lassevk 的用户发布的

Answer 1

该代码正在计算来自 1 的数字的最小公倍数至 20 (或您使用的任何其他 range)。

从1开始, 然后对于每个数字 k在该范围内，它检查是否 k是 i 的因数，如果不是(即当 i % k > 0 时)，它会将该数字作为一个因素添加。

但是做i *= k不会产生最小公倍数，因为例如当你有i = 2和 k = 6乘以 i 就足够了通过 3有 i % 6 == 0 , 所以内循环找到最小的数字 j这样 i*j有k作为一个因素。

到底每一个数k在范围内是 i % k == 0为此，我们总是添加最小因子，因此我们计算了最小公倍数。

---

也许准确显示值如何变化有助于理解过程:

i = 1
k = 1
i % k == 0  -> next loop

i = 1
k = 2
i % k == 1 > 0
   j = 1
   if (i*j) % k == 1 -> next inner loop
   j = 2
   if (i*j) % k == 0
      i *= j
i = 2
k = 3
i % k == 2 > 0
    j = 1
    if (i*j) % k == 2 -> next inner loop
    j = 2
    if (i*j) % k == 4 % 3 == 1 -> next inner loop
    j = 3
    if (i*j) % k == 6 % 3 == 0
        i *= j
i = 6
k = 4
i % k == 2 > 0
    j = 1
    if (i*j) % k == 6 % k == 2 -> next inner loop
    j = 2
    if (i*j) % k == 12 % k == 0
        i *= j
i = 12
k = 5
i % k == 2 > 0
    j = 1
    if (i*j) % k == 12 % k == 2 -> next inner loop
    j = 2
    if (i*j) % k == 24 % k == 4 -> next inner loop
    j = 3
    if (i*j) % k == 36 % k == 1 -> next inner loop
    j = 4
    if (i*j) % k == 48 % k == 3 -> next inner loop
    j = 5
    if (i*j) % k == 60 %k == 0
       i *= j
i = 60
...

您可以立即注意到一些事情:

• range(1, 21)可以安全地更改为 range(2, 21)自 1什么都不做
• 每次 k是一个质数当 j=k 时内部循环结束最终会出现在 i *= k .这是从什么时候开始预料到的 k是素数，它没有因数，所以没有选择更小的数 j那将使i k 的倍数.
• 在其他情况下号码i乘以一个数j < k使得 k 的所有因素现在在 i .