Getting the unique factors of a number recursively

I have written the below code to get the unique factors. Please offer suggestions for better results.

#Python program to print out all ways to multiply smaller integers 
#that equal the original number, without repeating sets of factors



def print_factors_list(dividend, factorstring, predivisor):
"""This function takes a number and prints the factors"""


   divisor = dividend - 1
   #Looping to get the factors
   for i in range(divisor, 1, -1 ):

      if dividend % i != 0:
        continue

      if i > predivisor:
        continue
      #Get the quotient for the multipying number   
      quotient = dividend / i


      if quotient <= i:
         if quotient <= predivisor:
            print factorstring + str(i) + "*" + str(quotient)
      print_factors_list(quotient, str(factorstring) + str(i) + "*", i)




#Check if the number is greater than 0
def print_factors(x):
# Check if the number is greater than 0 
    if (x < 0):
        print "Enter a positive integer"
    #Check if the number is 0
    elif (x == 0):
        print "Enter a positive integer"
    #Go to the function print_factors_list for further evaluation
    else:
    #Print the default factors(the number itself and 1)
       print str(x) + "*" + str(1)
       print_factors_list(x, "", x )




#Take input from the user
num = int(input("Enter a number: "))
#Call the function with the number given by the user
print_factors(num)

An alternative (and probably more efficient) approach would be to derive all prime factors (hint: you could use divmod) and then create each of the possible factorings from that (hint: you could use itertools combinations).

Some notes:

1. If you extract prime factors from smallest to largest, the remainder will always either be prime or be a composite with a smallest prime factor greater than or equal to the last one found.

2. One can also use the fact that all of the prime numbers except 2 are odd numbers to step through quickly.

3. The largest possible prime factor of any integer n

   $n$

   $n$ may be discovered by examining no more than n−−√

   $\sqrt{n}$

   $sqrt{n}$ potential factors.

You might want to peek at this question for a Python-based prime factoring program.

Getting all factors from prime factorization

Starting with an example 60, we can easily determine that its prime factorization p = [2, 2, 3, 5]. Clearly, this is one possible factorization, which can easily be output in Python 3 as

print(*p, sep=' * ')

If you’re using 2.6 or 2.7, you can still use this neat syntax, but you’ll have to do this instead

from __future__ import print_function
print(*p, sep=' * ')

This prints:

2 * 2 * 3 * 5

So now all you need to do is create all possible unique lists of factors. So for each two-factor combination, you could use this:

for i in itertools.permutations(p,len(p)):
    print(*[i[0],reduce(lambda x,y:x*y,i[1:])],sep=' * ')

That creates a list of all such two-factor combinations with exactly one prime factor, but they are not unique. Because there is a repeated factor of 2 in the list, the product “2 * 30” is printed twice. One way to handle this is to store each factor as it’s used and suppress printing of non-unique factors.

Similarly, all non-unique 3-factor combinations with one prime factor:

for i in itertools.permutations(p,len(p)):
    print(*[i[0],i[1],reduce(lambda x,y:x*y,i[2:])],sep=' * ')

Or alternatively:

for i in itertools.permutations(p,len(p)):
    print(*(list(i[:2])+[reduce(lambda x,y:x*y,i[2:])]),sep=' * ')

This should give you enough of a clue as to how you might generate all possible factorizations. A recursive approach is probably even better here.

Also, as an incidental note, factorings with 1 are typically omitted as trivial.

Focusing on refactoring of your current idea rather than making any radical changes, you could:

1. note that we are only interested in divisors which are less than or equal to the predivisor, and adjust the range to exclude all values of the divisor that don’t satisfy this.

2. turn print_factors_list into a generator yielding all the lists of factors, and do all the actual printing in print_factors. This (along with a couple of other minor changes) makes the code more readable, in my view.

.

def get_factors_list(dividend, ceiling = float('infinity')):
    """ Yield all lists of factors where the largest is no larger than ceiling """
    for divisor in range(min(ceiling, dividend - 1), 1, -1):
        quotient, mod = divmod(dividend, divisor)
        if mod == 0:
            if quotient <= divisor:
                yield [divisor, quotient]
            for factors in get_factors_list(quotient, divisor):
                yield [divisor] + factors

def print_factors(x):
    if x > 0:
        for factors in get_factors_list(x):
            print '*'.join(map(str, factors))
    else:
        print "Enter a positive number"