在 Python 中找到一个数字的所有因数的最有效方法是什么? [英] What is the most efficient way of finding all the factors of a number in Python?

问题描述

有人可以向我解释在 Python (2.7) 中找到一个数字的所有因数的有效方法吗?

我可以创建一个算法来做到这一点，但我认为它的编码很差，并且需要很长时间才能产生大量的结果.

解决方案

from functools import reduce定义因素(n):返回集(减少(列表.__添加__，([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

这将很快返回一个数字 n 的所有因子.

为什么以平方根为上限?

sqrt(x) * sqrt(x) = x.因此，如果两个因数相同，则它们都是平方根.如果您将一个因素放大，则必须使另一个因素变小.这意味着两者之一将始终小于或等于 sqrt(x)，因此您只需搜索到该点即可找到两个匹配因子之一.然后你可以使用 x/fac1 得到 fac2.

reduce(list.__add__, ...) 将 [fac1, fac2] 的小列表合并成一个长列表.>

[i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0 返回一对因数，如果余数当您将 n 除以较小的时为零(它也不需要检查较大的；它只是通过将 n 除以较小的来获得.)

外面的 set(...) 正在消除重复，这只会发生在完美的正方形上.对于 n = 4，这将返回 2 两次，所以 set 去掉其中之一.

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.

解决方案

from functools import reduce

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, which only happens for perfect squares. For n = 4, this will return 2 twice, so set gets rid of one of them.

这篇关于在 Python 中找到一个数字的所有因数的最有效方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！