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?
Advertisement
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:
- As the first factor decreases, the second factor increases, giving you the second half of the list in increasing order.
- 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]