# Produce all multiples of a set of primes up to a certain limit

I have some Python code that generates all possible multiples and combinations of a given set of primes up to a certain limit. The code runs and does exactly what I intend it to do, now I am trying to optimize it in order to improve run-time.

import math
from collections import defaultdict
import itertools

lim = 10**13 #This limit can be changed if you'd like
primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47] #So can these primes
res = defaultdict(list)
res[()] = [1] #Maybe not this

for n in range(1, len(primes) + 1):
for combo in itertools.combinations(primes, n):
for c in res[combo[:(n - 1)]]:
stop = int(math.log(lim / c, combo[-1]))
for x in range(1, stop + 1):
res[combo[:n]].append(c * combo[-1] ** x)

multiples = []
for key in res:
multiples += res[key]

multiples.sort()
print(multiples)


If you don't feel like reading through all that, the basic idea is to take increasingly large combinations of the set of primes, starting with a single prime, and computing all the permutations of the subset with increasing powers up to the chosen limit. The way I have it coded, I am initializing the dictionary with an empty tuple that maps to the number 1 as it makes writing the rest of the for loop much easier.

For example: Let's say your list of primes is $[2,3,5]$ and your limit is 30. First, it's going to take each number in that list and compute all the powers below 30, storing each in a dictionary key that maps to a list. So, after one loop, you would have:

res = {(): [1], (2):[2,4,8,16], (3):[3,9,27], (5):[5,25]}


The second time through the combinations would be ${2 \choose 3}$, ${2 \choose 5}$, and ${3 \choose 5}$. In each combo, it chops off the last value and searches for the key associated with the remaining part of the tuple. So for ${2 \choose 3}$ it will look for the (2) key, i.e. the powers of two, and multiply them by increasing powers of three until they go above thirty. So you will have:

${2 \choose 3}$ = $[2 \cdot 3, 2 \cdot 9, 4 \cdot 3, 8 \cdot 3]$ = $[6, 18, 12, 24]$

This process continues until you are out of combinations.

For lower limits the code actually runs fairly quickly. For high limits ($10^{13}$, 20 primes) like I have listed above the code runs in about 5 minutes. I would like to get that down to under a minute if possible. I was wondering if I could turn the main for loop into a dictionary comprehension but I'm not sure if that's possible since I've initialized res outside of the main for loop, and need the () = [1] for my code to run.

I am not completely married to this idea, but I do think it's slick (I'm still pretty new to programming so we might have different ideas on what that means), so if I could preserve it that would be nice. Any ideas?

• Give variables better names, exponent is better than x.
• List comprehensions make your code more understandable.
• You can use dictionary.values() to get a list of the values.
• You should make this a function. If you can change; limit, and primes.
• You're not just getting multiples, you're also getting exponents too. So you may want a better function / variable name.

This can get you:

from collections import defaultdict
from itertools import combinations
from math import log

def prime_multiples(limit, primes):
res = defaultdict(list)
res[()] = [1]

for n in range(1, len(primes) + 1):
for combo in combinations(primes, n):
base = combo[-1]
res[combo] = [
multiple * base**exponent
for multiple in res[combo[:-1]]
for exponent in range(1, int(log(limit / multiple, base)) + 1)
]

multiples = [i for val in key.values() for i in val]
multiples.sort()
return multiples

print(prime_multiples(10**13, [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]))


It's 5AM, and I've not tested the following in anyway.
But you could probably change the code to use the modulo operator, %. To check if the number is devisable. And so if you write a generator function, you may be able to use:

def prime_multiples(limit, primes):
yield 1
for num in range(1, limit):
if any(num % prime == 0 for prime in primes):
yield num