Project Euler Problem 005
Statement
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?
Solution
The technique I used to solve this problem is quite simple. You need to find the LCM(Least Common Multiple)
of the first 20 numbers.
To do this I set up a list with them, and then starting from the second(2) I pass through the list(from the next
that I have taken) dividing the others in case it's possible. This way i take all the prime factors that are already
taken into account.
if __name__ == '__main__': n = 20 lt = list(range(1, n+1)) for i in range(1, n): x = lt[i] index = i + 1 while index < n: if (lt[index] % x) == 0: lt[index] //= x index += 1 result = 1 for elem in lt: result *= elem print("The result is:", result)
The Python code is available for download here.