How to get all the factors of a number n when I know all the factors of the square root of n?

I have an algorithm that returns a list of all the factors of the n but only checks up to sqrt(n). However, I am aware that one can get the factors of n using only the list of factors of sqrt(n).

Function:

def get_factors(n):
    sqrtn = floor(sqrt(n))
    factors = []

    factors.append(1)
    for factor in range(2, sqrtn):
        if n % factor == 0:
            factors.append(factor)
    factors.append(sqrtn)
    
    return factors

The code above returns [1, 2, 4, 5, 10] for an input of n=100, but I need to manipulate the list returned after the function call and make it [1, 2, 4, 5, 10, 20, 25, 50, 100] (all the factors of n). I only have a vague idea of that the list returned by the function is only the left-half of the whole list of factors. How would I approach this programatically?

Answer

I think that you’re looking for this:

start = -2 if n // factors[-1] == factors[-1] else -1
factors.extend(n // f for f in factors[start::-1])

For any pair of numbers n = a * b, it must be the case that one of a, b must be less than or equal to sqrt(n) and one must be greater than or equal to it. Rearranging the definition gives a = n // b, where // is Python’s floor division operator that guarantees that your result stays an integer.

Notice that I suggest iterating over the list backwards. This has two advantages in your case:

1. As the first factor decreases, the second factor increases, giving you the second half of the list in increasing order.
2. It is unwise to modify a list during iteration. This applies to an explicit loop or to the lazy iterator I am passing to extend here. Getting a slice of the list effectively makes a copy, so you are no longer modifying in-place.

For your concrete example:

>>> factors = [1, 2, 4, 5, 10]
>>> n = 100
>>> start = -2 if n // factors[-1] == factors[-1] else -1
>>> factors.extend(n // f for f in factors[start::-1])
>>> factors
[1, 2, 4, 5, 10, 20, 25, 50, 100]

And another:

>>> factors = [1, 5, 13]
>>> n = 325
>>> start = -2 if n // factors[-1] == factors[-1] else -1
>>> factors.extend(n // f for f in factors[start::-1])
>>> factors
[1, 5, 13, 25, 65, 325]