0
\$\begingroup\$

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()
\$\endgroup\$
1
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Mohammed Javed Akhtar Aug 29 '18 at 17:23
  • \$\begingroup\$ 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/… \$\endgroup\$ – AChampion Aug 29 '18 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.