5
\$\begingroup\$

I was asked this question in an interview:

Find all the factors of a given natural number, N

1 <= N <= 10**10

Example:

N = 6 => 1, 2, 3, 6

N = 60 => 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

I wrote following code,but got an feedback that complexity could be improved.

How to optimise following code?

import math
def get_all_factors(n):
    ans = [1]
    if n==1:
        return ans
    factors = [False] * n
    for i in xrange(2,int(math.sqrt(n))):
        if not factors[i]:
            if n%i == 0:
                factors[i] = True
                factors[n/i] = True


    for i, is_factor in enumerate(factors[1:], 1):
        if is_factor:
            ans.append(i)
    ans.append(n)
    return ans        

ans = get_all_factors(60)
print [x for x in ans]
\$\endgroup\$
5
\$\begingroup\$

You don't need to keep an intermediate list here, just add all the divisors to a set:

from math import sqrt

def get_all_factors(n):
    divisors = set()
    for i in xrange(1, int(sqrt(n)) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n / i)
    return divisors

if __name__ == "__main__":
    print get_all_factors(60)

I also added a if __name__ == "__main__": guard to allow importing this function from another script.

Note that there is no requirement for the output to be a sorted list in the problem statement you posted. If there is, you can just call sorted on the output of this.

As @kyrill mentioned in the comments, you could also make this a generator:

from math import sqrt, ceil

def get_all_factors(n):
    sqrt_n = sqrt(n)
    for i in xrange(1, int(ceil(sqrt_n))):
        if n % i == 0:
            yield i
            yield n / i
    if sqrt_n % 1 == 0:
        yield int(sqrt_n)
\$\endgroup\$
1
\$\begingroup\$

The following algorithm is a bit shorter, doesn't need the math module (it uses / and // divisions instead) or any other module, and uses less if statements.

def get_all_factors(n):
    factor_list = []
    test_i = 1
    upper_limit = n       # consistent with n/test_i below when test_i = 1
    while test_i <= upper_limit:
        if n % test_i == 0:
            factor_list.append(test_i)
            factor_list.append(n//test_i)
        test_i += 1
        upper_limit = n/test_i
    return list(set(factor_list))   # remove duplicates and sort (e.g. dup 3 when n is 9)

print(get_all_factors(60))

#--> [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]

It works by testing numbers sequentially (test_i iterating from 1) and also by shortening the maximum possible factor (variable upper_limit) using the division result after each test_i. For more detail in how it works, just run it in debug mode and follow the evolution of variables and lists.

Best regards.

Note: Runs fine in Python3. Minor float and int conversions needed to make it run in Python2 due to difference of / behavior.

\$\endgroup\$

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.