# Printing all the factors as well as the prime factors of a given number using Python 2.7.x

Okay here is my maiden attempt at programming using Python 2.7. I need help or feedback on this code:

1. How do I know about the processing cycles this program consumes?
2. How do I implement this idea using recursion?
3. What's the best way of removing duplicate items fom a list. I am not happy with this

#remove the duplicate elements in the list
set_of_factors = set(list_of_all_quotients)
list_of_all_quotients = list(set_of_factors)
return list_of_all_quotients


The design constraints are the following:

1. The prime numbers are to be generated at the run time.
2. All composite (non-prime) factors are to be derived from prime factors only.

Here goes the code:

#-------------------This Function would find all the prime factors of a given number-------------

def find_prime_factors(number):
list_of_prime_factors = []
quotient = number
while (quotient > 1):
if(quotient % 2 == 0):
#check whether the quotient is even?
list_of_prime_factors.append(2)
quotient = quotient / 2

else:
#if the quotient is odd
for index in xrange (3, 1 + (number/2),2):
#start the for loop at 3 and end at a number around one-half of the quotient, and test with odd numbers only
if (quotient % index == 0 ):
list_of_prime_factors.append(index)
quotient = quotient / index

else:
#The number isn't even and there are no odd numbered factors for it, that is it's a prime.
break
#-------------------------------------

return list_of_prime_factors

#-------------------This Function would find quotients that would result by dividing the number by it's prime factors------------------

def find_all_quotients(number, list_of_prime_factors = []):
list_of_all_quotients = []

dividend = number
for index in list_of_prime_factors:
dividend = dividend / index
list_of_all_quotients.append(index)
list_of_all_quotients.append(dividend)

if (len(list_of_all_quotients) == 0):
return list_of_all_quotients
else:
#if the last item in the list is 1, then remove it:
if(list_of_all_quotients[-1] == 1 ):list_of_all_quotients.pop()
#remove the duplicate elements in the list
set_of_factors = set(list_of_all_quotients)
list_of_all_quotients = list(set_of_factors)
return list_of_all_quotients

#This Function would find all the factors of a number
#--by using it's prime factors and quotients (derived by dividing it by it's prime factors)

def find_all_factors(number, list_of_prime_factors = [] ,list_of_all_quotients = []):
list_of_all_factors = list_of_all_quotients

for otr_index in range(0, len(list_of_prime_factors) ):
for inr_index in range(0, len(list_of_all_factors)):
product = list_of_prime_factors[otr_index] * list_of_all_factors[inr_index]
if (number % product == 0 and number != product): list_of_all_factors.append(product)

if (len(list_of_all_factors) == 0):
return list_of_all_factors
else:
#if the last item in the list is 1, then remove it:
if(list_of_all_factors[-1]==1): list_of_all_factors.pop()
#remove the duplicate elements in the list
set_of_factors = set(list_of_all_factors)
list_of_all_factors = list(set_of_factors)
return list_of_all_factors

#-------------------This Function would print all the prime factors of a given number------------

def print_factors(number, list_to_be_printed=[], separator=''):

if (len(list_to_be_printed) == 0) :
#No roots - means a prime number:
if (separator == ''):
print"\n\nTry again",
else:
print"\n\nOops {} is a prime number! So, it doesn't have any prime factors except for 1 and iself. ".format(number)
#Composite Number:
else:
factors = list_to_be_printed
factors.sort()
if separator == '':
#The separator isn't specified or empty, means print all factors separated by space:
print "\n\nAll the Factors for {} would be = ".format(number),
for index in xrange (0, len(factors)):
print "{}".format(factors[index]),
if (index + 1 == len(factors)):
pass
else:
print separator,
else:
#Some separator is specified, use that, and print prime numbers:
print "\n\nThe Prime Factorization for {} would be = ".format(number),
for index in xrange (0, len(factors)):
print "{}".format(factors[index]),
if (index + 1 == len(factors)):
pass
else:
print separator,

#-------------------The Main Function Block-------------------------------------------------------

def main():
str_product = raw_input("Please enter a number to get its factors ")
int_product = int(str_product)

#------------------------------------------------------------------

prime_factors = find_prime_factors(int_product)
print_factors(int_product, prime_factors,'X')
quotients = find_all_quotients(int_product, prime_factors)
all_factors = find_all_factors(int_product, prime_factors,quotients)
print_factors(int_product, all_factors,'')

#-----------------------------------------------------------------

if __name__ == "__main__":
main()


A couple of stylistic comments and python gotchas:

If you are just starting out in Python I would look to use Py3 and if you can't use Py3, use some of the __future__ imports to ensure you are writing code that is compatible and behaves the same, e.g.:

from __future__ import print_function   # print(...)
from __future__ import division         # a / b - float division, a // b - integer division


This will make the transition to Py3 easier.

I find it very hard to read when you have if statements that are collapsed on one line and especially if there is no empty line afterwards, e.g.:

    if(list_of_all_quotients[-1] == 1 ):list_of_all_quotients.pop()
#remove the duplicate elements in the list
set_of_factors = set(list_of_all_quotients)


Also, you don't need parens () around if expressions, e.g. above:

    if list_of_all_quotients[-1] == 1:
list_of_all_quotients.pop()

#remove the duplicate elements in the list
set_of_factors = set(list_of_all_quotients)


Having a pass block in the if condition can be removed by just checking the negative of the condition, e.g.:

     if (index + 1 == len(factors)):
pass
else:
print separator,


Can be replaced with:

     if index+1 != len(factors):
print separator,


You have to be very careful with mutable default arguments (see: “Least Astonishment” and the Mutable Default Argument). In many cases you don't need the default argument in your code as it is required for the call to succeed.
E.g. In general, you would be only able to call this function once without passing in list_to_printed or the next call would give you unexpected results but you usage doesn't have this problem because you always pass in the list (suggest you remove the default argument):

def print_factors(number, list_to_be_printed=[], separator=''):


Why do you want to do this recursively? Recursive algorithms tend to have good partitioning of the problem into smaller sub problems - factorization doesn't feel like that is the case. Python's default recursion depth is relatively low and python doesn't perform recursion optimisations that other languages designed for recursion perform, so you often pay a penalty for recursion (call stack).

Overall the algorithmic complexity is much higher than it needs to be. An easier way to find prime factors is to have a good reliable algorithm for generating primes:

Here's a relatively simple prime number generator:

import itertools as it

def primes():
yield 2
sieve = {}
for n in it.count(3, 2):
if n not in sieve:
sieve[n*n] = 2*n
yield n
continue
a = sieve.pop(n)
x = n + a
while x in sieve:
x += a
sieve[x] = a


Then to get the prime factors of a number:

def prime_factors(n):
for p in primes():
while n % p == 0:
n //= p
yield p
if p*p > n:
break
if n > 1:
yield n

In []:
list(prime_factors(120))

Out[]:
[2, 2, 2, 3, 5]


You can use a collections.Counter to hold both the factors and exponents, e.g.

In []:
from collections import Counter
pfactors = Counter(prime_factors(120))
pfactors

Out[]:
Counter({2: 3, 3: 1, 5: 1})


So now the unique primes are pfactors.keys() and their exponents are pfactors.values():

You can then you this to generate all the factors from the primes and their exponents, by multplying together all the primes with every combination of exponent up to pfactor.values()

In []:
factors = []
for exponents in it.product(*[range(e+1) for e in pfactors.values()]):
factor = 1
for prime, exponent in zip(pfactors.keys(), exponents):
factor *= prime**exponent
factors.append(factor)

factors

Out[]:
[1, 5, 3, 15, 2, 10, 6, 30, 4, 20, 12, 60, 8, 40, 24, 120]


You can obviously sort it with sorted() e.g.:

In []:
sorted(factors)

Out[]:
[1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120]

• Thank you so much for such a detailed and positively critical analysis. You have answered all my questions except for this one, "How do I know about the processing cycles this program consumes?" Any pointers on that one too, would be highly appreciated. Thanks again. – Mohammed Javed Akhtar Aug 29 '18 at 17:23
• Are you wanting to the Big-O complexity - look at your loops, how does that loop relate to the input, if it is linear then it is O(n) if you have loop within a loop then you would have to multiply the ns, so you would O(n*n) or O(n^2), etc. If you want to know what resources it consumes then there are several modules out there for doing more profiling, e.g. see jakevdp.github.io/PythonDataScienceHandbook/… – AChampion Aug 29 '18 at 17:46