# Problem 5

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 positive number that is evenly divisible by all of the numbers from 1 to 20?

The most obvious number which would be divisible by 1-20 would be n-factorial (n!).  Obviously this would not be the smallest possible number or the question would be too simple.  What can be eliminated?  If you have 2 x 5 then the number will be divisible by 10 without having to multiply by 10.  This leads to the idea that only the prime factors are necessary.  But what about 12?  The prime factors are 2 and 3, but a number which includes 2 x 3 only will not necessarily be divisible by 12.  Thus you need all the repeated prime factors as well.  So we need to multiply all the prime factors of each number, including repeated factors for the composite to be divisible by each number.

# Solution

`#!/usr/bin/pythonimport sysfrom primes import factordef union(a,b):    for each in a:        if a.count(each)&gt;0 and b.count(each)&gt;0:            b.remove(each)    return a + bif __name__ == '__main__':    #Determines the smallest number divisible by each of a range of numbers    #smaller than just n!    val = int(sys.argv)#Bad practice, assumes input is an int    factors = []    for each in range (2,val+1):        factors = union(factors,factor(each))    composite = 1    for each in factors:        composite = composite * each    print (composite)`

Prime factors with repeats are [2, 3, 2, 5, 7, 2, 3, 11, 13, 2, 17, 19].

The answer is 232792560.  (n! is 2432902008176640000)

# Approach

I start by defining a "union" function.  In set theory, the union adds two sets together but doesn't repeat the common members of the set.  My approach was to compare the two sets and remove the repeats from one of the sets as I went along.  Then I can simply concatenate the remaining sets without overlap.

# Benchmarks

The surprising result here was the poor performance of pypy.  In this case, pypy was slower than either Python 2 or 3.  I even repeated the tests to see if the computer happened to be busy when pypy was running.  With this program, pypy performed almost as slowly as Jython.

`Problem #5 Benchmarkstime python primes20.py 2000151117794877444315...real 0m0.902suser 0m0.896ssys 0m0.004stime python -O primes20.py 2000151117794877444315...real 0m0.945suser 0m0.928ssys 0m0.016stime python3 primes20.py 2000151117794877444315...real 0m1.253suser 0m1.252ssys 0m0.000stime python3 -O primes20.py 2000151117794877444315...real 0m1.276suser 0m1.264ssys 0m0.008stime pypy primes20.py 2000151117794877444315...real 0m2.520suser 0m2.508ssys 0m0.004stime pypy -O primes20.py 2000151117794877444315...real 0m2.511suser 0m2.504ssys 0m0.004stime jython primes20.py 2000151117794877444315...real 0m3.102suser 0m5.984ssys 0m0.104s`

# Conclusion

This was an interesting twist on the prime factoring problem from earlier.  I had to modify the factoring code I had written not to throw away repeated prime factors.  Pypy had a surprisingly poor performance in this program and the "count" function used in my union subroutine may be implemented poorly in pypy.