JalxP - 3 months ago 6x

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

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`1`

s 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`

.

Source (Stackoverflow)

Comments