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
That code is computing the least common multiple of the numbers from
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.
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
3 to have
i % 6 == 0, so the inner loop finds the least number
j such that
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:
range(1, 21)can be safely changed to
range(2, 21)since the
1s never do anything
kis a prime number the inner loop ends when
j=kand will end up in
i *= k. That's expected since when
kis a prime it has no factors and so there's no option for a smaller number
jthat would make
ia multiple of
iis multiplied by a number
j < kso that all factors of
kare now in