Michael - 1 year ago 34

Python Question

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)`

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!

Answer

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.

Source (Stackoverflow)