algorithm - Understanding a solution to the Euler Project in Python -

i'm going through euler project. i've started using javascript , i've switched python yesterday, got stuck in problem seemed complex solve javascript solved in python, , i've decided start first problem again in python.

i'm @ problem 5 asks me find smallest positive number evenly divisible of numbers 1 20.

i know how solve paper , pencil , i've solved using programming, in search optimising crossed solution in forum of euler project.

it seems elegant , fast, ridiculous fast compared mine, takes 2 seconds solve same problem numbers 1 1000, mine takes several minutes.

i've tried understand it, i'm still having difficulty grasp doing. here is:

i = 1 k in (range(1, 21)):     if % k > 0:         j in range(1, 21):             if (i*j) % k == 0:                 *= j                 break print 

it posted user named lassevk

that code computing least common multiple of numbers 1 20 (or whichever other range use).

it starts 1, each number k in range checks if k factor of i, , if not (i.e. when i % k > 0) adds number factor.

however doing i *= k not produce least common multiple, because example when have i = 2 , k = 6 it's enough multiply i 3 have i % 6 == 0, inner loop finds least number j such i*j has k factor.

in end every number k in range such i % k == 0 , added minimal factors in order so, computed least common multiple.

---

maybe showing how values change can understanding process:

i = 1 k = 1 % k == 0  -> next loop  = 1 k = 2 % k == 1 > 0    j = 1    if (i*j) % k == 1 -> next inner loop    j = 2    if (i*j) % k == 0       *= j = 2 k = 3 % 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         *= j = 6 k = 4 % k == 2 > 0     j = 1     if (i*j) % k == 6 % k == 2 -> next inner loop     j = 2     if (i*j) % k == 12 % k == 0         *= j = 12 k = 5 % 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        *= j = 60 ... 

you can notice few things:

• the range(1, 21) can safely changed range(2, 21) since 1s never anything
• everytime k prime number inner loop ends when j=k , end in i *= k. that's expected since when k prime has no factors , there's no option smaller number j make i multiple of k.
• in other casesthe number i multiplied number j < k factors of k in i.