All possible pairs of factors

Question

I am trying to write a program that takes a number with a single leading integer and an arbitrary number of trailing zeros and then prints all possible combinations of two factors.

ie.

100

factors are 2^2, 5^2

so the program would print:

(2,50),(4,25),(5,20)

or

600

factors are 2^3,3,5^2

(2,300),(4,150),(8,75),(3,200),(5,120),(25,24),(6,100),(12,50),(15,40),(30,20),(60,10)

...I think that's all of them? Is it? I could use a program to check...

import itertools

facts=[[2,2,2],[3],[5,5]]
for n in itertools.product(*facts)
    print(n)

I see that I am using this incorrectly but that was my first stab at it.

This just gives (2,3,5) ten times.

I want something like (2) * (2,3,5,5) and (2,2) * (3,5.5) and the like...

Answer 1

To generate all factors of a number given its prime factors:

#!/usr/bin/env python
import itertools, operator

def all_factors(prime_dict):
    series = [[p**e for e in range(maxe+1)] for p, maxe in prime_dict.items()]
    for multipliers in itertools.product(*series):
        yield reduce(operator.mul, multipliers)

Example

prime_dict = {2:3, 3:1, 5:2}
L = sorted(all_factors(prime_dict))
number_of_divisors = reduce(lambda prod, e: prod*(e+1), prime_dict.values(),1)
assert len(L) == number_of_divisors
# -> [1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24,
#     25, 30, 40, 50, 60, 75, 100, 120, 150, 200, 300, 600]

To produce pairs:

n, isodd = divmod(len(L), 2)
print(zip(L[:n], reversed(L[n + isodd:])))
if isodd: # number is perfect square
   print((L[n], L[n]))

Output

[(1, 600), (2, 300), (3, 200), (4, 150), (5, 120), (6, 100),
 (8, 75), (10, 60), (12, 50), (15, 40), (20, 30), (24, 25)]

It works for small numbers. You could use it to test your solution that could take into account the special form of your numbers: x00000...

Answer 2

Here's how I would do it:

def factors(n):
  # Fill this in

def factor_pairs(n):
  for i in factors(n):  # You need to write the factor() function
    yield i, n / i

if __name__ == '__main__':
  n = input('Enter an integer: ')

  for i, j in factor_pairs(n):
    print i, j

I'm not going to code it for you entirely, but you get the idea.

Answer 3

I think this would do what you want:

n = input('Enter a number? ')
factors = []

for i in range(int(sqrt(n))):
  if n % i == 0:
    factors.append((i, n / i))

By the definition of factors, the maximum number you have to check is up to the square root of the number, so if you can code this, you should be set.

If you can code this, you should be set.

Answer 4

You can put it all in a list comprehension

import math
n = 600 # or whatever...
[(x, n/x) for x in range(1, int(math.sqrt(n))+1) if n % x == 0]

Returns:

[(1, 600), (2, 300), (3, 200), (4, 150), (5, 120), (6, 100), (8, 75), (10, 60), (12, 50), (15, 40), (20, 30), (24, 25)]

If you don't want (1,600) just use range(2, int(math.sqrt(n))+1).