(a) The first improvement to this algorithm is given by the function factors1(), below. Within IPython, this function can be written in the default text editor and initialized using the %edit magic :
def factors1(n):
facs = set()
for i in range(1, int(math.sqrt(n)) + 1):
if not n % i:
facs |= {i, n // i}
return facs
By adding both the number i which is found to be a factor of n and n // i (which is also a factor of n) it is not necessary to test values of \texttt{i} greater than the square root of n: such values will already have been included as n // i. We use a set() so that values for which i and n // i are equal are not duplicated in the output.
To time it, call it with some large(ish) integer using the %timeit magic:
In [x]: %timeit factors1(123456789)
1000 loops, best of 3: 1.33 ms per loop
(b) The same algorithm can be coded using a generator expression:
def gen_factors2(n):
yield 1
for i in range(2, int(math.sqrt(n)) + 1):
if not n % i:
yield i
yield n // i
yield n
def factors2(n):
return set(gen_factors2(n))
but does not lead to a significantly different execution time:
In [131]: %timeit factors2(123456789)
1000 loops, best of 3: 1.27 ms per loop
(Generators are very memory efficient but cannot generally be expected to be faster than list comprehensions.)