Find all the factors of a given natural number, N

Question

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]

Answer 1

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)

Answer 2

The following algorithm is a bit shorter, doesn't need the math module (it uses / and // divisions instead) or any other module, and uses fewer 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.

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