1
\$\begingroup\$

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.

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

1 Answer 1

2
\$\begingroup\$

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

instead:

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

    for num in factorss(n):
        for i in range(twos):
            yield num*(2**i)

You'll have to multiply each of the factors returned with the factors of two that the original number contained. But you remove the need to check even numbers, ending up with only the faster of the two ways your code can go.

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Jun 25, 2018 at 12:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.