CODEWITHSUNDEEP
pythonmath
Peregrine
Peregrine

Reputation: 367

All possible pairs of factors

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...

Upvotes: 1

Views: 2503

Answers (4)

jfs
jfs

Reputation: 414149

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...

Upvotes: 2

Sean Redmond
Sean Redmond

Reputation: 4114

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).

Upvotes: 1

Jon Egeland
Jon Egeland

Reputation: 12613

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.

Upvotes: 0

Blender
Blender

Reputation: 298106

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.

Upvotes: 2

Related Questions