find all multiplicands and multipliers for a number
Dave Angel
d at davea.name
Fri Apr 10 21:16:57 EDT 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