find all multiplicands and multipliers for a number

Paul Rubin no.email at nospam.invalid
Fri Apr 10 21:28:01 EDT 2015


ravas <ravas at outlook.com> writes:
>     for divisor in range(1, end):
>         q, r = dm(dividend, divisor)
>         if r is 0:
>             rlist.append((divisor, q))

Use r == 0 instead of r is 0 there.  "r is 0" is object identity that
might happen to work but that's an implementation detail in the
interpreter.

> output: [(1, 999), (3, 333), (9, 111), (27, 37), (37, 27), (111, 9), (333, 3)]

> How do we describe this function? 

Listing the divisors of n

> Does it have an established name?

It's closely related to factoring.  The number of factors as a function
of n is called the Euler totient function, 

> What would you call it?

Enumerating the divisors.  Easier to do if you know the factors.

> Does 'Rosetta Code' have it or something that uses it?

Don't know.  Try their search function looking for factoring.

> Can it be written to be more efficient?

Yes, definitely.  Simplest is make a list of the factors and then
generate combinations of them.  Factor the number by trial division,
dividing out each factor as you find it, stopping when you get above the
square root of whatever is left.

There are fancier methods to factor even more efficiently and whole
books have been written about them, but the above is a start.

You might like www.projecteuler.net which has lots more of these
math-oriented exercises, though the later ones get pretty hard.



More information about the Python-list mailing list