-2

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.

1

Your program actually performs the classical Finding least common multiples by prime factorization algorithm.

The sequence of divisions remove from each number all prime factors lower in the array. The array ends up with only prime factors in the required number, so the whole product gives the right answer.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.