CODEWITHSUNDEEP
pythonalgorithmsortingfactors
Just some guy
Just some guy

Reputation: 1959

Python - Put factors of a number into an array in sorted order

I have written this algorithm that finds all factors of a given number and puts them into a list:

def find_all_factors(n):
    factors = []
    for i in range(1, floor(sqrt(n))+1):
        if n % i == 0:
            factors.append(i)
            cofactor = n // i
            if i != cofactor: factors.append(cofactor)
    return factors

Inside the list cofactors will be placed next to eachother, but I would like them to appear in sorted order instead. Example of output from algorithm above: for n = 36 it outputs [1, 36, 2, 18, 3, 12, 4, 9, 6]. I'm doing this as an exercise and I would like to know what the most efficient way of getting them in sorted order would be, any ideas?

You can see one of my solutions below. It works, but I don't think it's optimal.

def find_all_factors(n):
    lower_factors = []
    higher_factors = []
    for i in range(1, floor(sqrt(n))+1):
        if n % i == 0:
            lower_factors.append(i)
            cofactor = n // i
            if i != cofactor: higher_factors.append(cofactor)
    return lower_factors + [higher_factors[-i] for i in range(1, len(higher_factors)+1)]  #Reverses higher_factors.

Upvotes: 0

Views: 802

Answers (3)

hemraj
hemraj

Reputation: 1034

from math import floor, sqrt


def find_all_factors(n):
    factors = []
    for i in xrange(1, int(floor(sqrt(n)))+1):
        quotient, remainder = divmod(n, i)
        if remainder == 0:
            factors.append(i)
            if quotient not in factors:
                factors.append(quotient)
    return sorted(factors)

print find_all_factors(36)

output:[1, 2, 3, 4, 6, 9, 12, 18, 36]

Upvotes: 0

aghast
aghast

Reputation: 15310

The one thing you are missing is simpler and easier operations on your lists. There is a Python built-in for reversing a sequence: reversed.

So you can do:

return lower_factors + list(reversed(higher_factors))

Upvotes: 1

ᴀʀᴍᴀɴ
ᴀʀᴍᴀɴ

Reputation: 4528

Just simply return the sorted list:

return sorted(factors)

how ever if you dont like using sorted function simply change for loop range to (1,n+1) :

def find_all_factors(n):
    factors = []
    for i in range(1, n+1):
        if n % i == 0:
            factors.append(i)
    return factors

find_all_factors(12) # [1, 2, 3, 4, 6, 12]

another way is using bisect(most efficient way):

import bisect
def find_all_factors(n):
    factors = []
    for i in range(1, math.floor(math.sqrt(n))+1):
        if n % i == 0:
            bisect.insort(factors,i)
            cofactor = n // i
            if i != cofactor: bisect.insort(factors, cofactor)
    return factors

find_all_factors(12) # [1, 2, 3, 4, 6, 12]

Insert in this module is O(n) however search is O(log(n))

Upvotes: 1

Related Questions