在Python中理解Euler项目的解决方案

Question

我目前正在经历欧拉项目.我已经开始使用JavaScript了,昨天我已经切换到Python,因为我陷入了一个似乎很复杂的问题,用Javascript解决但很容易用Python解决,所以我决定从第一个问题开始蟒蛇.

我遇到问题5,它要求我找到最小的正数,它可以被1到20的所有数字整除.

我知道如何使用纸和笔来解决它,我已经使用编程解决了问题,但是为了优化它,我在欧拉项目的论坛中越过了这个解决方案.

它看起来很优雅,与我的相比它速度相当快,很荒谬,因为解决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.