find all multiplicands and multipliers for a number

Dave Angel d at davea.name
Sat Apr 11 03:16:57 CEST 2015


On 04/10/2015 09:06 PM, Dave Angel wrote:
> 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
>
>
And

http://rosettacode.org/wiki/Prime_decomposition#Python

There the function that you should grok is  decompose()

-- 
DaveA



More information about the Python-list mailing list