Problem 5 - Smallest Number Divisible By 1 to 20

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/python

import sys
from primes import factor

def union(a,b):
    for each in a:
        if a.count(each)>0 and b.count(each)>0:
            b.remove(each)
    return a + b

if __name__ == '__main__':
    #Determines the smallest number divisible by each of a range of numbers
    #smaller than just n!
    val = int(sys.argv[1])#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 Benchmarks
time python primes20.py 2000

151117794877444315...

real 0m0.902s
user 0m0.896s
sys 0m0.004s
time python -O primes20.py 2000

151117794877444315...

real 0m0.945s
user 0m0.928s
sys 0m0.016s
time python3 primes20.py 2000

151117794877444315...

real 0m1.253s
user 0m1.252s
sys 0m0.000s
time python3 -O primes20.py 2000

151117794877444315...

real 0m1.276s
user 0m1.264s
sys 0m0.008s
time pypy primes20.py 2000

151117794877444315...

real 0m2.520s
user 0m2.508s
sys 0m0.004s
time pypy -O primes20.py 2000

151117794877444315...

real 0m2.511s
user 0m2.504s
sys 0m0.004s
time jython primes20.py 2000

151117794877444315...

real 0m3.102s
user 0m5.984s
sys 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.