Find all the factors of a given natural number, N I was asked this question in an interview:

Find all the factors of a given natural number, N
1 &lt;= N &lt;= 10**10
Example:
N = 6 =&gt; 1, 2, 3, 6
N = 60 =&gt; 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]
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)