lcminv problem - find all numbers b such that lcm(a, b) == l

lcminv.py

from fractions import gcd

def lcm(a, b):
	"""Least common multiple"""
	return a * b // gcd(a, b)

def factor(n):
	"""Factor natural number into primes and their powers"""
	factors = {}
	
	# simplest and slowest possible prime factoring algorithm
	k = 2
	while n > 1:
		if n % k == 0:
			factors[k] = factors.get(k, 0) + 1
			n /= k
		else:
			k += 1
	
	return factors

def build(Bs):
	"""Build a set of numbers from primes and allowed powers"""
	if len(Bs) == 0:
		return set([1])
	
	p = list(Bs.keys())[0] # get any prime used
	qs = Bs.pop(p) 

	ns = build(Bs) # numbers built without picked prime
	ns2 = set() # combined numbers
	for n in ns:
		for q in qs:
			ns2.add(n * (p ** q)) # combine numbers
	
	return ns2

def lcminv(l, a):
	"""Find all numbers b such that lcm(a, b) == l"""
	L = factor(l)
	A = factor(a)

	Bs = {}
	for p in (L.keys() | A.keys()): # combined list of primes
		pL = L.get(p, 0) # p's power in L
		pA = A.get(p, 0) # p's power in A

		# theoretically: max(pA, pB) == pL
		if pL == pA: # pL comes from a, free choice for b
			Bs[p] = list(range(0, pA))
		elif pL > pA: # pL comes from b, one choice for b
			Bs[p] = [pL]
		else: # impossible case
			Bs[p] = []
	
	return build(Bs)