Adnan Adnan - 1 year ago 50
Python Question

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

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

I can create algorithms to do this job, but i think it is poorly coded, and takes too long to execute a result for a large numbers.

agf agf
Answer Source
def factors(n):    
    return set(reduce(list.__add__, 
                ([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. I think this only happens for perfect squares. For n = 4, this will return 2 twice, so set gets rid of one of them.

Edit: sqrt is actually faster than **0.5, but I'll leave it out as it's nice as a self-contained snippet.