Understanding a solution to the Euler Project in Python

Question

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 1

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.