# 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 <= 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]


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:
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)


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.