获得所有除数的最佳方法是什么？

Question

这是非常愚蠢的方式:

def divisorGenerator(n):
    for i in xrange(1,n/2+1):
        if n%i == 0: yield i
    yield n

我想得到的结果类似于这个,但我想要一个更聪明的算法(这个太慢和愚蠢了:-)

我可以足够快地找到素数因子及其多样性.我有一个以这种方式生成因子的生成器:

(factor1,multiplicity1)(factor2,multiplicity2)
(
factor3,multiplicity3)
等......

即输出

for i in factorGenerator(100):
    print i

是:

(2, 2)
(5, 2)

我不知道这对我想做什么有用多少(我将其编码用于其他问题),无论如何我想要一个更聪明的方法来制作

for i in divisorGen(100):
    print i

输出这个:

1
2
4
5
10
20
25
50
100

---

更新:非常感谢Greg Hewgill和他的"智能方式":)计算所有100,00000的除数用他的方式对着我的机器上的愚蠢方式的39s,非常酷:D

更新2:停止说这是这篇文章的副本.计算给定数的除数数不需要计算所有除数.这是一个不同的问题,如果你认为它不是在维基百科上寻找"除数函数".在发布之前阅读问题和答案,如果你不明白什么是主题,只是不添加没有用的已经给出的答案.

Answer 1

鉴于您的factorGenerator函数,这里有一个应该工作的divisorGen:

def divisorGen(n):
    factors = list(factorGenerator(n))
    nfactors = len(factors)
    f = [0] * nfactors
    while True:
        yield reduce(lambda x, y: x*y, [factors[x][0]**f[x] for x in range(nfactors)], 1)
        i = 0
        while True:
            f[i] += 1
            if f[i] <= factors[i][1]:
                break
            f[i] = 0
            i += 1
            if i >= nfactors:
                return

该算法的整体效率将完全取决于factorGenerator的效率.

Answer 2

为了扩展Shimi所说的内容,你应该只运行从1到n的平方根的循环.然后找到这对,做n / i,这将涵盖整个问题空间.

还有人指出,这是一个NP,或"困难"的问题.穷举搜索,你正在做的方式,就像保证答案一样好.加密算法等使用这一事实来帮助保护它们.如果有人要解决这个问题,那么大多数(如果不是全部)我们当前的"安全"通信都会变得不安全.

Python代码:

import math

def divisorGenerator(n):
    large_divisors = []
    for i in xrange(1, int(math.sqrt(n) + 1)):
        if n % i == 0:
            yield i
            if i*i != n:
                large_divisors.append(n / i)
    for divisor in reversed(large_divisors):
        yield divisor

print list(divisorGenerator(100))

哪个应输出如下列表:

[1, 2, 4, 5, 10, 20, 25, 50, 100]

Answer 3

虽然已经有很多解决方案,但我真的要发布这个:)

这个是:

• 可读
• 短
• 自包含,复制和粘贴准备
• 快速(在有很多素因子和除数的情况下,比接受的解决方案快10倍)
• python3,python2和pypy兼容

码:

def divisors(n):
    # get factors and their counts
    factors = {}
    nn = n
    i = 2
    while i*i <= nn:
        while nn % i == 0:
            factors[i] = factors.get(i, 0) + 1
            nn //= i
        i += 1
    if nn > 1:
        factors[nn] = factors.get(nn, 0) + 1

    primes = list(factors.keys())

    # generates factors from primes[k:] subset
    def generate(k):
        if k == len(primes):
            yield 1
        else:
            rest = generate(k+1)
            prime = primes[k]
            for factor in rest:
                prime_to_i = 1
                # prime_to_i iterates prime**i values, i being all possible exponents
                for _ in range(factors[prime] + 1):
                    yield factor * prime_to_i
                    prime_to_i *= prime

    # in python3, `yield from generate(0)` would also work
    for factor in generate(0):
        yield factor

Answer 4

我想你可以停下math.sqrt(n)来而不是n/2.

我会举例说明你可以轻松理解它.现在sqrt(28)是5.29这样的ceil(5.29)将是6.所以如果我将在6点停止然后我将得到所有的除数.怎么样？

首先看代码,然后看图像:

import math
def divisors(n):
    divs = [1]
    for i in xrange(2,int(math.sqrt(n))+1):
        if n%i == 0:
            divs.extend([i,n/i])
    divs.extend([n])
    return list(set(divs))

现在,请看下图:

可以说,我已经添加1到我的除数名单,我开始用i=2这样

所以在所有迭代结束时,因为我已将商和除数添加到我的列表中,所有28的除数都被填充.

希望这可以帮助.如果您有任何疑问,请不要犹豫,我会很乐意帮助您:).

来源:如何确定一个数字的
半径除数 - 代码和图像

Answer 5

我喜欢Greg解决方案,但我希望它更像python.我觉得它会更快,更具可读性; 所以在经过一段时间的编码之后,我就出来了.

需要前两个函数来制作列表的笛卡尔积.并且只要出现这个问题就可以重复使用.顺便说一句,我必须自己编程,如果有人知道这个问题的标准解决方案,请随时与我联系.

"Factorgenerator"现在返回一个字典.然后将字典输入"除数",使用它来首先生成列表列表,其中每个列表是具有p prime的形式p ^ n的因子列表.然后我们制作这些列表的笛卡尔积,我们最终使用Greg的解决方案来生成除数.我们对它们进行排序,并将其归还.

我测试了它,它似乎比以前的版本快一点.我测试它作为一个更大的程序的一部分,所以我不能说真的更快多少.

Pietro Speroni(pietrosperoni点吧)

from math import sqrt


##############################################################
### cartesian product of lists ##################################
##############################################################

def appendEs2Sequences(sequences,es):
    result=[]
    if not sequences:
        for e in es:
            result.append([e])
    else:
        for e in es:
            result+=[seq+[e] for seq in sequences]
    return result


def cartesianproduct(lists):
    """
    given a list of lists,
    returns all the possible combinations taking one element from each list
    The list does not have to be of equal length
    """
    return reduce(appendEs2Sequences,lists,[])

##############################################################
### prime factors of a natural ##################################
##############################################################

def primefactors(n):
    '''lists prime factors, from greatest to smallest'''  
    i = 2
    while i<=sqrt(n):
        if n%i==0:
            l = primefactors(n/i)
            l.append(i)
            return l
        i+=1
    return [n]      # n is prime


##############################################################
### factorization of a natural ##################################
##############################################################

def factorGenerator(n):
    p = primefactors(n)
    factors={}
    for p1 in p:
        try:
            factors[p1]+=1
        except KeyError:
            factors[p1]=1
    return factors

def divisors(n):
    factors = factorGenerator(n)
    divisors=[]
    listexponents=[map(lambda x:k**x,range(0,factors[k]+1)) for k in factors.keys()]
    listfactors=cartesianproduct(listexponents)
    for f in listfactors:
        divisors.append(reduce(lambda x, y: x*y, f, 1))
    divisors.sort()
    return divisors



print divisors(60668796879)

PS这是我第一次发布到stackoverflow.我期待着任何反馈.

Answer 6

一个说明性的 Pythonic 单行：

from itertools import chain
from math import sqrt

def divisors(n):
    return chain.from_iterable((i,n//i) for i in range(1,int(sqrt(n))+1) if n%i == 0)

但更好的是，只需使用 sympy：

from sympy import divisors

Answer 7

这是在纯 Python 3.6 中处理高达 10**16 左右的数字的一种智能而快速的方法，

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