Fix Python – What is the most efficient way of finding all the factors of a number in Python?

Question

Can someone explain to me an efficient way of finding all the factors of a number in Python (2.7)?

I can create an algorithm to do this, but I think it is poorly coded and takes too long to produce a result for a large number.

Now we will see solution for issue: What is the most efficient way of finding all the factors of a number in Python?

``````from functools import reduce

def factors(n):
([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))
``````

This will return all of the factors, very quickly, of a number `n`.

Why square root as the upper limit?

`sqrt(x) * sqrt(x) = x`. So if the two factors are the same, they’re both the square root. If you make one factor bigger, you have to make the other factor smaller. This means that one of the two will always be less than or equal to `sqrt(x)`, so you only have to search up to that point to find one of the two matching factors. You can then use `x / fac1` to get `fac2`.

The `reduce(list.__add__, ...)` is taking the little lists of `[fac1, fac2]` and joining them together in one long list.

The `[i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0` returns a pair of factors if the remainder when you divide `n` by the smaller one is zero (it doesn’t need to check the larger one too; it just gets that by dividing `n` by the smaller one.)

The `set(...)` on the outside is getting rid of duplicates, which only happens for perfect squares. For `n = 4`, this will return `2` twice, so `set` gets rid of one of them.

This question is answered By – agf