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

Question

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?

Answer 1

• 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