JalxP JalxP - 5 months ago 9
Python Question

Understanding a solution to the Euler Project in Python

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

Answer

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.