How to implement 2d array/odometer in python?

Question

I'm working on algorithm that finds all the factors of a number from its prime factors. Here's my code up to this point

def is_prime(x):
    return all(x % i for i in range(2, x))

def next_prime(x):
    return min([a for a in range(x+1, 2*x) if is_prime(a)])

def numFactors(n):

    factors = {1, n}
    primeFactors = dict()

    s = n
    while s != 1:
        # print(s)
        pr = 2
        while s % pr != 0:
            pr = next_prime(pr)
        if pr in primeFactors.keys():
            primeFactors[pr] += 1
        else:
            primeFactors[pr] = 1
        factors.add(pr)
        factors.add(int(s/pr))
        s = int(s/pr)

This code gives me a dictionary with all the prime factors and their exponent. So, for example, 120 gives {2: 3, 3: 1, 5: 1} What I'm trying to do get every factor like such: (2^1 * 3^0 * 5^0), (2^2 * 3^0 * 5^0)... which is more or less an odometer like this

(0 0 0)
(1 0 0)
(2 0 0)
(3 0 0)
(0 1 0)
(1 1 0)
(2 1 0)
...

How do I achieve this from the primeFactors values? I can't seem to put together the right loop combination, especially since each column has a different max int.

Answer 1

You can try itertools.product

from itertools import product

d = {2: 3, 3: 1, 5: 1}

keys = d.keys()
possibilies = ['*'.join([f'{j[0]}^{j[1]}' for j in zip(keys, i)]) for i in product(*[range(v+1) for v in d.values()])]

print(possibilies)

['2^0*3^0*5^0',
 '2^0*3^0*5^1',
 '2^0*3^1*5^0', 
'2^0*3^1*5^1', 
'2^1*3^0*5^0', 
'2^1*3^0*5^1', 
'2^1*3^1*5^0', 
'2^1*3^1*5^1', 
'2^2*3^0*5^0', 
'2^2*3^0*5^1', 
'2^2*3^1*5^0', 
'2^2*3^1*5^1', 
'2^3*3^0*5^0', 
'2^3*3^0*5^1', 
'2^3*3^1*5^0', 
'2^3*3^1*5^1']