了解Python中的Euler项目解决方案 [英] Understanding a solution to the Euler Project in Python

问题描述

我目前正在进行Euler项目。我开始使用JavaScript，昨天我改用Python，因为我陷入了一个问题，该问题似乎很难用Javascript解决，但在Python中很容易解决，因此我决定从第一个问题开始

我遇到了问题5，该问题要求我找到最小的正数，该正数可以被从1到20的所有数字均分。

我知道如何用纸和铅笔解决它，我已经使用编程解决了，但是为了进行优化，我在Euler Project论坛上使用了该解决方案。 / p>

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

我试图理解它，但是我仍然很难掌握它的实际作用。在这里是：

  i = 1 
对于k in（range（1，21））：
如果i％k> 0：j在范围（1，21）中的
：如果（i * j）％k == 0：
 
i * = j 
中断
打印i 
  

最初由名为 lassevk

的用户发布b $ b

解决方案

该代码正在计算 1 最小公倍数 $ c>到 20 （或您使用的其他任何范围）。

它从 1 开始，然后对于该范围内的每个 k ，它检查 k 是 i 的因数，如果不是（例如，当 i％k> 0



但是做 i * = k 不会产生最小的公共倍数，例如，当您有 i = 2 和 k = 6 将 i 乘以 3 足以使 i％6 == 0 ，因此内循环找到了叶t编号 j ，这样 i * j 的 k 为

最后，范围中的每个数字 k 使得 i ％k == 0 ，因此我们总是添加最小因子，因此我们计算了最小公倍数。

---

也许确切地显示了值的变化可以帮助理解该过程：

  i = 1 
k = 1 
i％k == 0->下一个循环
 
 i = 1 
 k = 2 
 i％k == 1>如果（i * j）％k == 1-> 0 
 j = 1 
下一个内循环
j = 2 
如果（i * j）％k == 0 
i * = j 
i = 2 
k = 3 
i％k = = 2>如果（i * j）％k == 2-> 0 
 j = 1 
下一个内循环
 j = 2 
如果（i * j）％k == 4％3 == 1->下一个内部循环
j = 3 
如果（i * j）％k == 6％3 == 0 
i * = j 
i = 6 
k = 4 
i％k == 2>如果（i * j）％k == 6％k == 2-> 0 
 j = 1 
下一个内循环
j = 2 
如果（i * j）％k == 12％k == 0 
i * = j 
i = 12 
k = 5 
i％k == 2>如果（i * j）％k == 12％k == 2-> 0 
 j = 1 
下一个内循环
 j = 2 
如果（i * j）％k == 24％k == 4->下一个内部循环
 j = 3 
如果（i * j）％k == 36％k == 1->下一个内循环
 j = 4 
如果（i * j）％k == 48％k == 3->下一个内部循环
j = 5 
如果（i * j）％k == 60％k == 0 
i * = j 
i = 60 
 ... 
  

您会立即注意到一些事情：

• 范围（1，21）可以安全地更改为范围（2，21）因为 1 永远不会做任何事


• 每次 k 都是质数内循环在 j = k 时结束，并以 i * = k 结尾。这是可以预期的，因为当 k 是素数时，它没有任何因素，因此没有选择较小的 j 将 i 设为 k 的倍数。


• 在其他情况下，数字 i 乘以 j< k ，这样所有 k 的因子现在都在 i 中。

I'm currently going through the Euler Project. I've started using JavaScript and I've switched to Python yesterday, as I got stuck in a problem that seemed to complex to solve with Javascript but easily solved in Python, and so I've decided to start from the first problem again in python.

I'm at problem 5 which asks me to find the smallest positive number that is evenly divisible by all of the numbers from 1 to 20.

I know how to solve it with paper and pencil and I've already solved using programming, but in a search for optimising it I crossed this solution in the forum of the Euler Project.

It seems elegant and it is fairly fast, ridiculous fast compared to mine, as it takes about 2 seconds to solve the same problem for numbers 1 to 1000, where mine takes several minutes.

I've tried to understand it, but I'm still having difficulty to grasp what it really is doing. Here it is:

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

It was originally posted by an user named lassevk

解决方案

That code is computing the least common multiple of the numbers from 1 to 20 (or whichever other range you use).

It starts from 1, then for each number k in that range it checks if k is a factor of i, and if not (i.e. when i % k > 0) it adds that number as a factor.

However doing i *= k does not produce the least common multiple, because for example when you have i = 2 and k = 6 it's enough to multiply i by 3 to have i % 6 == 0, so the inner loop finds the least number j such that i*j has k as a factor.

In the end every number k in the range is such that i % k == 0 and we always added the minimal factors in order to do so, thus we computed the least common multiple.

---

Maybe showing exactly how the values change can help understanding the process:

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
...

You can immediately notice a few things:

• The range(1, 21) can be safely changed to range(2, 21) since the 1s never do anything
• Everytime k is a prime number the inner loop ends when j=k and will end up in i *= k. That's expected since when k is a prime it has no factors and so there's no option for a smaller number j that would make i a multiple of k.
• In other casesthe number i is multiplied by a number j < k so that all factors of k are now in i.

这篇关于了解Python中的Euler项目解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！