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.
from primes import factor
for each in a:
if a.count(each)>0 and b.count(each)>0:
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)#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
Prime factors with repeats are [2, 3, 2, 5, 7, 2, 3, 11, 13, 2, 17, 19].
The answer is 232792560. (n! is 2432902008176640000)
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.
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
time python -O primes20.py 2000
time python3 primes20.py 2000
time python3 -O primes20.py 2000
time pypy primes20.py 2000
time pypy -O primes20.py 2000
time jython primes20.py 2000
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.