# Finding all factors of n efficiently

This function generates all factors of an input n.

It begins at the square root of n, and checks numbers down to zero. When a factor x is found, then another factor must be n divided by x.

Also, if n is odd, only odd numbers need to be checked.

from math import sqrt

def factors(n):
"""
Generates all factors of n. Iterates from sqrt(n) down to zero.
When a factor x is found, another factor must be n divided by x.
If n is odd, only odd numbers need to be checked.

>>> sorted(list(factors(1001)))
[1, 7, 11, 13, 77, 91, 143, 1001]
"""
root = sqrt(n)
start = int(root)  # Default starting number is sqrt(n)

if n % 2 == 0:
step = -1  # n is even, so check both evens and odds
else:
step = -2  # n is odd, so check only odds
start = start // 2 * 2 + 1  # Round start to odd number

if root.is_integer():
yield int(root)  # sqrt(n) is a factor of n
# Start at numbers < sqrt(n), so that sqrt(n) is not yielded twice
start += step

for x in range(start, 0, step):
if n % x == 0:
yield x
yield n // x


For example,

>>> sorted(list(factors(1000)))
[1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000]


This takes 31 iterations. But when the number is odd:

>>> sorted(list(factors(1001)))
[1, 7, 11, 13, 77, 91, 143, 1001]


This takes only 16 iterations.

I'm wondering if there are other tricks that could make the process more efficient.

• If so inclined you could use Euler Project 21 for references with other ways of finding the factors of a number. Commented Nov 25, 2016 at 18:46

For big numbers and for many numbers checking for divisibility with prime numbers under the sqrt will give a big speed increase, you could still use the same method. But there are many ways to optimize factorization, many many ways.

I like your code! But some styling notes and then a suggestion. I think the usual way to check if a number is a perfect square is:

if root*root == n:
yield int(root)
start += step


the check:

root.is_integer()


is more implicit and explicit is better.

Now, in line comments is hard to read. You shouldn't use those.

if n % 2 == 0:
step = -1  # n is even, so check both evens and odds
else:
step = -2  # n is odd, so check only odds
start = start // 2 * 2 + 1  # Round start to odd number


if n % 2 == 0:
# n is even, so check both evens and odds
step = -1
else:
# n is odd, so check only odds
step = -2
# Round start to odd number
start = start // 2 * 2 + 1


but even better would be to not repeat what the if statement already says.

if n % 2 == 0:
# only check evens
step = -1
else:
# check only odds
step = -2
# Round start to odd number
start = start // 2 * 2 + 1


start = start // 2 * 2 + 1


might be implicit, could be more readable:

start = int(root)
start += 1 if start % 2 == 0 else 0


Now to the suggestion

If with any number that is even, it has a number of factors 2. So remove the factors 2 and do you algorithm on that number. Like this:

def factors(n):
"""
Generates all factors of n. Iterates from sqrt(n) down to zero.
When a factor x is found, another factor must be n divided by x.
If n is odd, only odd numbers need to be checked.

>>> sorted(list(factors(1001)))
[1, 7, 11, 13, 77, 91, 143, 1001]
"""

root = sqrt(n)
step = -2
start = int(root)
start += 1 if start % 2 == 0 else 0

if root*root == n:
yield int(root)
start += step

for x in range(start, 0, step):
if n % x == 0:
yield x
yield n // x

def brigde(n):
twos = 1
while n % 2 == 0:
twos += 1
n //= 2


• About the first suggestion - (1) I think root.is_integer() is more explicit and better. (2) if root*root == n would cause the answer to be wrong. Try when n=27. Commented Jun 25, 2018 at 12:55