find all multiplicands and multipliers for a number

[Dave Angel]

On 04/10/2015 07:37 PM, ravas wrote:
> def m_and_m(dividend):
>      rlist = []
>      dm = divmod
>      end = (dividend // 2) + 1
>      for divisor in range(1, end):
>          q, r = dm(dividend, divisor)
>          if r is 0:
>              rlist.append((divisor, q))
>      return rlist
>
> print(m_and_m(999))
> ---
> output: [(1, 999), (3, 333), (9, 111), (27, 37), (37, 27), (111, 9), (333, 3)]
> ---
>
> How do we describe this function?
> Does it have an established name?
> What would you call it?
> Does 'Rosetta Code' have it or something that uses it?
> Can it be written to be more efficient?
> What is the most efficient way to exclude the superfluous inverse tuples?
> Can it be written for decimal numbers as input and/or output?
>
> Thank you!
>

I'd call those factors of the original number.  For completeness, I'd 
include (999,1) at the end.

If it were my problem, I'd be looking for only prime factors.  Then if 
someone wanted all the factors, they could derive them from the primes, 
by multiplying all possible combinations.

The program can be sped up most obviously by stopping as soon as you get 
a tuple where divisor > q.  At that point, you can just repeat all the 
items, reversing divisor and q for each item.  Of course, now I notice 
you want to eliminate them.  So just break out of the loop when divisor > q.

You can gain some more speed by calculating the square root of the 
dividend, and stopping when you get there.

But the real place to get improvement is to only divide by primes, 
rather than every possible integer.  And once you've done the division, 
let q be the next value for dividend.  So you'll get a list like

[3, 3, 3, 37]

for the value 999

See:
http://rosettacode.org/wiki/Factors_of_an_integer#Python


-- 
DaveA