Michael - 4 months ago 7
Python Question

# Solution to Euler Project Task 5: Why does it work?

After some trial and error I have found a solution which works very quickly for the Project Euler Problem 5. (I have found another way which correctly solved the example case (numbers 1-10) but took an eternity to solve the actual Problem.) Here it goes:

``````def test(n):
for x in range(2,21):
if n % x != 0:
return False
return True

def thwart(n):
for x in range(2,21):
if test(n/x):
n /= x
return n
raise TypeError

num = 1
for x in range(1,21):
num *= x

while True:
try:
num = thwart(num)
except TypeError:
break

print(num)
``````

My main problem is understanding why calling
`thwart(num)`
repeatedly is enough to result in the correct solution. (I.e. why is it able to find the SMALLEST number and doesnt just spit out any number divisible by the numbers 1-20?)
I only had some vague thoughts when programming it and was surprised at how quickly it worked. But now I have trouble figuring out why exactly it even works... The optimized solutions of other people on SO Ive found so far were all talking about prime factors which I can't see how that would fit with my program...?
Any help is appreciated! Thanks!

Well this isn't really a coding issue but a mathematical issue. If you look at all the numbers from 1-20 as the prime sthat make them you'll get the following: 1, 2,3,2^2,5,2^3,7,2^3....2^2*5. the interesting part here is that once you multiply by the highest exponent of every single factor in these numbers you will get a number that can be divided by each of the numbers between one and twenty. Once you realize that the problem is a simple mathematical one and approach it as such you can use this basic code:

``````import math
primes = [2]
for n in range(3,21): #get primes between 1 and 20
for i in primes:
if n in primes:
break
if n%i == 0:
break
if i> math.sqrt(n):
primes.append(n)
break
s = 1
for i in primes:
for j in range(10): # no reason for 10, could as well be 5 because 2^5 >20
if i**j > 20:
s = s*(i**(j-1))
break

print s
``````

Additionally, the hint that the number 2520 is the smallest number that can be divided by all numbers should make you understand how 2520 is chosen: I have taken a photo for you: As you can caculate, when you take the biggest exponents and multiply them you get the number 2520.

What your solution does your solution basically takes the number which is 1*2*3*4..*20 and tries dividing it by every number between 2 to 20 in such a way that it will still remain relevant. By running it over and over you remove the un-needed numbers from it. early on it will remove all the unnecessary 2's by dividing by 2, returning the number and then being called again and divided by 2 again. Once all the two's have been eliminated it will eliminate all the threes, once all the unnecessary threes will be eliminated it will try dividing by 4 and it will se it wont work, continue to 5, 6, 7... and when it finishes the loop without being able to divide it will raise a TypeError and you will finish your program with the correct number. This is not an efficient way to solve this problem but it will work with small numbers.