# How to explain this method to find the least common multiple of the first n natural numbers?

This is the Project Euler question #5. The statement is pretty much finding the least common multiple of the first n natural numbers. So for example, the least common multiple of 1, 2 .. 10 is 2520.

I admit I was just trying random stuff and I didn't expect the following to work (written in Python):

``````factors = int(input())
factorList = []

for i in range(2, factors+1):
factorList.append(i)

for i in range(len(factorList)-1):
for j in range(2*i+2, len(factorList), i+2):
factorList[j] //= factorList[i]

result = 1
for i in range(len(factorList)):
result *= factorList[i]

print (result)
``````

This program takes the input, such as 10. Then it will make a list of the numbers 2, 3 .. 10. After, it will iterate each element, then divide it off the proceeding elements at intervals of the element's value.

For example, it will start at 2, which will transform the array to 2, 3, 2, 5, 3, 7, 4, 9, 5 because 4, 6, 8, 10 were divided by 2. It will do the same with 3, then 2 again (4 became 2) until it finishes the second last item. When this is done running on input 10, the list looks like 2 3 2 5 1 7 2 3 1, which I then multiply together to get the answer.

This passed all the test cases, but I have no idea why it works. I really did not expect it to work. I understand that somehow the final list contains the maximum number of each prime factor from any single number (eg my example has 2*2*2 from 8 and 3*3 from 9), but I do not understand how it got there. The other solutions I've found to this question are all more intuitive, using the formula n!/(gcd(1..n)) and the property that gcd(a,b,c) = gcd(gcd(a,b),c).

If anyone could explain why this method is valid, I would appreciate it.