Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Date: Fri, 10 Apr 2015 21:16:57 -0400
From: Dave Angel <d@davea.name>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.5.0
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: find all multiplicands and multipliers for a number
References: <890bd388-f50a-4dec-9ef5-27715427472a@googlegroups.com> <55287387.4070501@davea.name>
In-Reply-To: <55287387.4070501@davea.name>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.210.1428715027.12925.python-list@python.org>
Lines: 65
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:88789

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