在Python中找到一个数字的所有因子的最有效的方法是什么?

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

有人能给我解释一种有效的方法来找出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.

我可以创建算法来完成这项工作，但我认为代码编写得很差，并且花费太长时间来执行大量的结果。

19 个解决方案

#1

from functools import reduce

def factors(n):    
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(pow(n, 0.5) + 1)) if n % i == 0)))

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

这将会很快地返回一个数字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.

sqrt(x) * sqrt(x) = x，所以如果两个因子相同，它们都是平方根。如果你使一个因素变大，你就必须使另一个因素变小。这意味着其中一个总是小于或等于sqrt(x)，所以你只需要搜索到那个点就能找到两个匹配的因子之一。然后你可以使用x / fac1得到fac2。

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

减少(列表。在一个长长的列表中，我们将列出[fac1, fac2]的小列表，并将它们组合在一起。

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.)

i (n /i) i的取值范围(1,int(sqrt(n)) + 1)如果n % i == 0，则返回一对因子，如果除以较小的n为0时的余数为零(不需要检查较大的n);它只是通过n除以较小的1得到的。

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.

外部的set(…)是去掉重复的，这只会发生在完美的方块上。对于n = 4，这将返回2次，所以设置删除其中一个。

#2

The solution presented by @agf is great, but one can achieve ~50% faster run time for an arbitrary odd number by checking for parity. As the factors of an odd number always are odd themselves, it is not necessary to check these when dealing with odd numbers.

@agf给出的解决方案很好，但是通过检查奇偶校验，可以实现一个任意奇数的更快的运行时间。由于奇数的因数本身都是奇数，所以在处理奇数时不需要检查这些因数。

I've just started solving Project Euler puzzles myself. In some problems, a divisor check is called inside two nested for loops, and the performance of this function is thus essential.

我自己已经开始解决Project Euler难题了。在一些问题中，在两个嵌套的for循环中调用一个除数检查，因此这个函数的性能是非常重要的。

Combining this fact with agf's excellent solution, I've ended up with this function:

将这个事实与agf的优秀解决方案结合起来，我就得到了这个函数:

from math import sqrt
def factors(n):
        step = 2 if n%2 else 1
        return set(reduce(list.__add__,
                    ([i, n//i] for i in range(1, int(sqrt(n))+1, step) if n % i == 0)))

However, on small numbers (~ < 100), the extra overhead from this alteration may cause the function to take longer.

然而，对于较小的数字(~ < 100)，此更改所带来的额外开销可能会使函数花费更长的时间。

I ran some tests in order to check the speed. Below is the code used. To produce the different plots, I altered the X = range(1,100,1) accordingly.

为了检查速度，我做了一些测试。下面是使用的代码。为了生成不同的图，我相应地改变了X = range(1,100,1)。

import timeit
from math import sqrt
from matplotlib.pyplot import plot, legend, show

def factors_1(n):
    step = 2 if n%2 else 1
    return set(reduce(list.__add__,
                ([i, n//i] for i in range(1, int(sqrt(n))+1, step) if n % i == 0)))

def factors_2(n):
    return set(reduce(list.__add__,
                ([i, n//i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0)))

X = range(1,100000,1000)
Y = []
for i in X:
    f_1 = timeit.timeit('factors_1({})'.format(i), setup='from __main__ import factors_1', number=10000)
    f_2 = timeit.timeit('factors_2({})'.format(i), setup='from __main__ import factors_2', number=10000)
    Y.append(f_1/f_2)
plot(X,Y, label='Running time with/without parity check')
legend()
show()

X = range(1,100,1)

X =范围(1100 1)

No significant difference here, but with bigger numbers, the advantage is obvious:

在这里没有明显的区别，但是有更大的数字，优势是显而易见的:

X = range(1,100000,1000) (only odd numbers)

X = range(1,100000,1000)(只有奇数)

X = range(2,100000,100) (only even numbers)

X =范围(2,100000,100)(只有偶数)

X = range(1,100000,1001) (alternating parity)

X =范围(1,100000,1001)(交替性)

#3

agf's answer is really quite cool. I wanted to see if I could rewrite it to avoid using reduce(). This is what I came up with:

agf的答案真的很酷。我想看看我是否可以重写它以避免使用reduce()。这就是我想到的:

import itertools
flatten_iter = itertools.chain.from_iterable
def factors(n):
    return set(flatten_iter((i, n//i) 
                for i in range(1, int(n**0.5)+1) if n % i == 0))

I also tried a version that uses tricky generator functions:

我还尝试了一个使用复杂的生成器函数的版本:

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

I timed it by computing:

我用计算来计时:

start = 10000000
end = start + 40000
for n in range(start, end):
    factors(n)

I ran it once to let Python compile it, then ran it under the time(1) command three times and kept the best time.

我运行它一次，让Python编译它，然后在时间(1)命令下运行它，并保持最好的时间。

• reduce version: 11.58 seconds
• 降低版本:11.58秒
• itertools version: 11.49 seconds
• itertools版本:11.49秒
• tricky version: 11.12 seconds
• 棘手的版本:11.12秒

Note that the itertools version is building a tuple and passing it to flatten_iter(). If I change the code to build a list instead, it slows down slightly:

请注意，itertools版本正在构建一个tuple并将其传递给扁平化()。如果我更改代码来构建一个列表，它会稍微慢一些:

• iterools (list) version: 11.62 seconds
• iterools(列表)版本:11.62秒。

I believe that the tricky generator functions version is the fastest possible in Python. But it's not really much faster than the reduce version, roughly 4% faster based on my measurements.

我相信复杂的生成器函数版本是Python中最快的。但它的速度并不比reduce版本快得多，大约比我的测量快4%。

#4

An alternative approach to agf's answer:

agf回答的另一种方法是:

def factors(n):    
    result = set()
    for i in range(1, int(n ** 0.5) + 1):
        div, mod = divmod(n, i)
        if mod == 0:
            result |= {i, div}
    return result

#5

Further improvement to afg & eryksun's solution. The following piece of code returns a sorted list of all the factors without changing run time asymptotic complexity:

进一步改善afg & eryksun的解决方案。下面这段代码返回一个已排序的所有因素列表，而不改变运行时的渐近复杂性:

    def factors(n):    
        l1, l2 = [], []
        for i in range(1, int(n ** 0.5) + 1):
            q,r = n//i, n%i     # Alter: divmod() fn can be used.
            if r == 0:
                l1.append(i) 
                l2.append(q)    # q's obtained are decreasing.
        if l1[-1] == l2[-1]:    # To avoid duplication of the possible factor sqrt(n)
            l1.pop()
        l2.reverse()
        return l1 + l2

Idea: Instead of using the list.sort() function to get a sorted list which gives nlog(n) complexity; It is much faster to use list.reverse() on l2 which takes O(n) complexity. (That's how python is made.) After l2.reverse(), l2 may be appended to l1 to get the sorted list of factors.

Idea:不是使用list.sort()函数来获得一个排序的列表，它给出了nlog(n)的复杂性;在l2上使用list.reverse()要快得多。(这就是python的制作方式。)在l2.reverse()之后，可以将l2添加到l1中，以获得排序的因子列表。

Notice, l1 contains i-s which are increasing. l2 contains q-s which are decreasing. Thats the reason behind using the above idea.

注意，l1包含了i-s。l2包含的q-s在减少。这就是使用上述想法的原因。

#6

I've tried most of these wonderful answers with timeit to compare their efficiency versus my simple function and yet I constantly see mine outperform those listed here. I figured I'd share it and see what you all think.

我试着用时间来比较它们的效率与我的简单功能，但我经常看到我的表现胜过那些列在这里的。我想我应该和大家分享一下，看看你们的想法。

def factors(n):
    results = set()
    for i in xrange(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            results.add(i)
            results.add(int(n/i))
    return results

As it's written you'll have to import math to test, but replacing math.sqrt(n) with n**.5 should work just as well. I don't bother wasting time checking for duplicates because duplicates can't exist in a set regardless.

就像它写的那样，你必须输入数学来测试，但是用n**代替math.sqrt(n)。5也应该工作。我不会浪费时间检查重复，因为副本不可能存在于集合中。

#7

Here's an alternative to @agf's solution which implements the same algorithm in a more pythonic style:

这里有一个替代@agf的解决方案，它以更python的风格实现了相同的算法:

def factors(n):
    return set(
        factor for i in range(1, int(n**0.5) + 1) if n % i == 0
        for factor in (i, n//i)
    )

This solution works in both Python 2 and Python 3 with no imports and is much more readable. I haven't tested the performance of this approach, but asymptotically it should be the same, and if performance is a serious concern, neither solution is optimal.

这个解决方案在Python 2和Python 3中都可以使用，没有导入，而且可读性更好。我还没有测试这种方法的性能，但是渐进地它应该是相同的，如果性能是一个严重的问题，那么这两个解决方案都不是最佳的。

#8

Be sure to grab the number larger than sqrt(number_to_factor) for unusual numbers like 99 which has 3*3*11 and floor sqrt(99)+1 == 10.

一定要获取比sqrt(number_to_factor)更大的数字，比如99，它有3*3*11和floor sqrt(99)+1 == 10。

import math

def factor(x):
  if x == 0 or x == 1:
    return None
  res = []
  for i in range(2,int(math.floor(math.sqrt(x)+1))):
    while x % i == 0:
      x /= i
      res.append(i)
  if x != 1: # Unusual numbers
    res.append(x)
  return res

#9

There is an industry-strength algorithm in SymPy called factorint:

有一种叫做factorint的工业强度算法:

>>> from sympy import factorint
>>> factorint(2**70 + 3**80) 
{5: 2,
 41: 1,
 101: 1,
 181: 1,
 821: 1,
 1597: 1,
 5393: 1,
 27188665321L: 1,
 41030818561L: 1}

This took under a minute. It switches among a cocktail of methods. See the documentation linked above.

这花了不到一分钟。它在各种方法之间切换。请参阅上面链接的文档。

Given all the prime factors, all other factors can be built easily.

考虑到所有的主要因素，所有其他因素都可以很容易地建立起来。

---

Note that even if the accepted answer was allowed to run for long enough (i.e. an eternity) to factor the above number, for some large numbers it will fail, such the following example. This is due to the sloppy int(n**0.5). For example, when n = 10000000000000079**2, we have

请注意，即使被接受的答案被允许运行足够长的时间(也就是永恒)来分解上述数字，对于一些大的数字，它也会失败，例如下面的例子。这是由于松散的int(n**0.5)。例如，当n = 10000000000000079**2时，我们有。

>>> int(n**0.5)
10000000000000078L

Since 10000000000000079 is a prime, the accepted answer's algorithm will never find this factor. Note that it's not just an off-by-one; for larger numbers it will be off by more. For this reason it's better to avoid floating-point numbers in algorithms of this sort.

因为10000000000000079是一个质数，所以被接受的答案的算法永远不会找到这个因子。请注意，这不仅仅是一个次要的问题;对于更大的数字，它将会被更多。出于这个原因，最好避免这种算法中的浮点数。

#10

Here is another alternate without reduce that performs well with large numbers. It uses sum to flatten the list.

这是另一种没有减少的替代，它在大量的情况下表现良好。它用sum来平放列表。

def factors(n):
    return set(sum([[i, n//i] for i in xrange(1, int(n**0.5)+1) if not n%i], []))

#11

Here is an example if you want to use the primes number to go a lot faster. These lists are easy to find on the internet. I added comments in the code.

这里有一个例子，如果你想用质数来加快速度。这些列表在互联网上很容易找到。我在代码中添加了注释。

# http://primes.utm.edu/lists/small/10000.txt
# First 10000 primes

_PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 
        31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 
        73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 
        127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 
        179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 
        233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 
        283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 
        353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 
        419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 
        467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 
        547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 
        607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 
        661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 
        739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 
        811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 
        877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 
        947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 
# Mising a lot of primes for the purpose of the example
)


from bisect import bisect_left as _bisect_left
from math import sqrt as _sqrt


def get_factors(n):
    assert isinstance(n, int), "n must be an integer."
    assert n > 0, "n must be greather than zero."
    limit = pow(_PRIMES[-1], 2)
    assert n <= limit, "n is greather then the limit of {0}".format(limit)
    result = set((1, n))
    root = int(_sqrt(n))
    primes = [t for t in get_primes_smaller_than(root + 1) if not n % t]
    result.update(primes)  # Add all the primes factors less or equal to root square
    for t in primes:
        result.update(get_factors(n/t))  # Add all the factors associted for the primes by using the same process
    return sorted(result)


def get_primes_smaller_than(n):
    return _PRIMES[:_bisect_left(_PRIMES, n)]

#12

Using set(...) makes the code slightly slower, and is only really necessary for when you check the square root. Here's my version:

使用set(…)使代码稍微慢一些，并且只有在检查平方根时才真正需要。这是我的版本:

def factors(num):
    if (num == 1 or num == 0):
        return []
    f = [1]
    sq = int(math.sqrt(num))
    for i in range(2, sq):
        if num % i == 0:
            f.append(i)
            f.append(num/i)
    if sq > 1 and num % sq == 0:
        f.append(sq)
        if sq*sq != num:
            f.append(num/sq)
    return f

The if sq*sq != num: condition is necessary for numbers like 12, where the square root is not an integer, but the floor of the square root is a factor.

条件对于像12这样的数字来说是必要的，因为平方根不是整数，但是平方根的下限是一个因数。

Note that this version doesn't return the number itself, but that is an easy fix if you want it. The output also isn't sorted.

注意，这个版本并没有返回数字本身，但是如果您想要的话，这是一个简单的修复。输出也没有排序。

I timed it running 10000 times on all numbers 1-200 and 100 times on all numbers 1-5000. It outperforms all the other versions I tested, including dansalmo's, Jason Schorn's, oxrock's, agf's, steveha's, and eryksun's solutions, though oxrock's is by far the closest.

我计时它运行10000次，在所有数字1-200和100，在所有数字1-5000。它比我测试过的所有其他版本都要出色，包括dansalmo's, Jason Schorn's, oxrock's, agf's, steveha's和eryksun的解决方案，尽管oxrock的方法是最接近的。

#13

Use something as simple as the following list comprehension, noting that we do not need to test 1 and the number we are trying to find:

使用简单到以下列表理解的东西，注意到我们不需要测试1和我们试图找到的数字:

def factors(n):
    return [x for x in range(2, n//2+1) if n%x == 0]

In reference to the use of square root, say we want to find factors of 10. The integer portion of the sqrt(10) = 4 therefore range(1, int(sqrt(10))) = [1, 2, 3, 4] and testing up to 4 clearly misses 5.

关于平方根的使用，我们要找出10的因数。sqrt(10) = 4的整数部分因此范围(1,int(10)) =[1, 2, 3, 4]和测试4显然是5。

Unless I am missing something I would suggest, if you must do it this way, using int(ceil(sqrt(x))). Of course this produces a lot of unnecessary calls to functions.

除非我遗漏了什么，否则我建议，如果你必须这样做，使用int(ceil(x))。当然，这会产生很多不必要的函数调用。

#14

a potentially more efficient algorithm than the ones presented here already (especially if there are small prime factons in n). the trick here is to adjust the limit up to which trial division is needed every time prime factors are found:

一种潜在的更有效的算法(特别是在n中有小的质数因子的情况下)。这里的技巧是，在每次找到质数因子时，对需要的极限进行调整:

def factors(n):
    '''
    return prime factors and multiplicity of n
    n = p0^e0 * p1^e1 * ... * pk^ek encoded as
    res = [(p0, e0), (p1, e1), ..., (pk, ek)]
    '''

    res = []

    # get rid of all the factors of 2 using bit shifts
    mult = 0
    while not n & 1:
        mult += 1
        n >>= 1
    if mult != 0:
        res.append((2, mult))

    limit = round(sqrt(n))
    test_prime = 3
    while test_prime <= limit:
        mult = 0
        while n % test_prime == 0:
            mult += 1
            n //= test_prime
        if mult != 0:
            res.append((test_prime, mult))
            if n == 1:              # only useful if ek >= 3 (ek: multiplicity
                break               # of the last prime) 
            limit = round(sqrt(n))  # adjust the limit
        test_prime += 2             # will often not be prime...
    if n != 1:
        res.append((n, 1))
    return res

this is of course still trial division and nothing more fancy. and therefore still very limited in its efficiency (especially for big numbers without small divisors).

当然，这仍然是审判部门，没有什么比这更花哨的了。因此，它的效率仍然非常有限(特别是对于没有小除数的大数字)。

this is python3; the division // should be the only thing you need to adapt for python 2 (add from __future__ import division).

这是python3;该部门//应该是您唯一需要适应python 2(来自__future__ import division)的东西。

#15

For n up to 10**16 (maybe even a bit more), here is a fast pure Python 3.6 solution,

对于n到10**16(甚至更多)，这里有一个快速纯Python 3.6解决方案，

from itertools import compress

def primes(n):
    """ Returns  a list of primes < n for n > 2 """
    sieve = bytearray([True]) * (n//2)
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = bytearray((n-i*i-1)//(2*i)+1)
    return [2,*compress(range(3,n,2), sieve[1:])]

def factorization(n):
    """ Returns a list of the prime factorization of n """
    pf = []
    for p in primeslist:
      if p*p > n : break
      count = 0
      while not n % p:
        n //= p
        count += 1
      if count > 0: pf.append((p, count))
    if n > 1: pf.append((n, 1))
    return pf

def divisors(n):
    """ Returns an unsorted list of the divisors of n """
    divs = [1]
    for p, e in factorization(n):
        divs += [x*p**k for k in range(1,e+1) for x in divs]
    return divs

n = 600851475143
primeslist = primes(int(n**0.5)+1) 
print(divisors(n))

#16

This is my solution to the problem:

这是我解决这个问题的方法:

Note that this will take longer for bigger numbers. The only problem is that I only know how to program in Python 3.x. I think that the only thing that needs changing is input() to raw_input().

请注意，这将花费更长的时间来获得更大的数字。唯一的问题是，我只知道如何在Python 3.x中编程。我认为唯一需要更改的是输入()到raw_input()。

# Sets the number
num = int(input("Enter number to be tested."))

for i in range(1,num): # Tests all numbers from 1 to the num
    while (num % i) == 0: ''' If the remainder of the number when it is divided by i is 0'''
        print(i) # Prints i
        break # Stops it from repeating one number infinitely
else: # After the previous process if done, do this
    print("Finished") # Says that the process is finished

input ("Press return/enter to close the program") ''' Closes the program after pressing enter'''

#17

I think for readability and speed @oxrock's solution is the best, so here is the code rewritten for python 3+:

我认为对于可读性和速度@oxrock的解决方案是最好的，所以这里是为python 3+编写的代码:

def num_factors(n):
    results = set()
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0: results.update([i,int(n/i)])
    return results

#18

Without using the reduce() which is not a built-in function in Python3:

不使用reduce()，它不是Python3中的内置函数:

def factors(n):
    return list(sorted(set([f(x) for x in range(1, int(n**0.5) + 1) if not n % x 
                for f in (lambda x: x, lambda x: n // x)])))

#19

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)))
if __name__ == "__main__":
       n = int(input("enter the number to get factors"))
       fact = list(factors(n))
       for x in fact:
              print(x)