获取数的所有除数的最佳方法是什么?

问题:获取数的所有除数的最佳方法是什么?

这是非常愚蠢的方式:

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

我想要得到的结果与此类似,但是我想要一个更智能的算法(这个算法太慢而且太笨了:-)

我可以很快找到主要因素及其多样性。我有一个生成器以这种方式生成因子:

(因数1,多重性1)(因数
2,多重性2)
(因数3,多重性3)
等等…

即输出

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和他的“智能方式” :)计算100000000的所有除数,而用39s的方式计算了我的机器上愚蠢的方式花费了0.01s,这很酷:D

更新2:别说这是这篇文章的重复。计算给定数的除数无需计算所有除数。这是一个不同的问题,如果您认为不是这样,那么请在Wikipedia上查找“除数函数”。在发布之前,请先阅读问题和答案,如果您不明白主题是什么,请不要添加无用且已经给出答案的内容。

Here’s the very dumb way:

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

The result I’d like to get is similar to this one, but I’d like a smarter algorithm (this one it’s too much slow and dumb :-)

I can find prime factors and their multiplicity fast enough. I’ve an generator that generates factor in this way:

(factor1, multiplicity1)
(factor2, multiplicity2)
(factor3, multiplicity3)
and so on…

i.e. the output of

for i in factorGenerator(100):
    print i

is:

(2, 2)
(5, 2)

I don’t know how much is this useful for what I want to do (I coded it for other problems), anyway I’d like a smarter way to make

for i in divisorGen(100):
    print i

output this:

1
2
4
5
10
20
25
50
100

UPDATE: Many thanks to Greg Hewgill and his “smart way” :) Calculating all divisors of 100000000 took 0.01s with his way against the 39s that the dumb way took on my machine, very cool :D

UPDATE 2: Stop saying this is a duplicate of this post. Calculating the number of divisor of a given number doesn’t need to calculate all the divisors. It’s a different problem, if you think it’s not then look for “Divisor function” on wikipedia. Read the questions and the answer before posting, if you do not understand what is the topic just don’t add not useful and already given answers.


回答 0

给定您的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

Given your factorGenerator function, here is a divisorGen that should work:

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

The overall efficiency of this algorithm will depend entirely on the efficiency of the factorGenerator.


回答 1

要扩展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]

To expand on what Shimi has said, you should only be running your loop from 1 to the square root of n. Then to find the pair, do n / i, and this will cover the whole problem space.

As was also noted, this is a NP, or ‘difficult’ problem. Exhaustive search, the way you are doing it, is about as good as it gets for guaranteed answers. This fact is used by encryption algorithms and the like to help secure them. If someone were to solve this problem, most if not all of our current ‘secure’ communication would be rendered insecure.

Python code:

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

Which should output a list like:

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

回答 2

尽管已经有很多解决方案,但我确实必须发布此内容:)

这是:

  • 可读的
  • 自包含,可复制并粘贴
  • 快速(在有很多主要因素和因数的情况下,比公认的解决方案快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

Although there are already many solutions to this, I really have to post this :)

This one is:

  • readable
  • short
  • self contained, copy & paste ready
  • quick (in cases with a lot of prime factors and divisors, > 10 times faster than the accepted solution)
  • python3, python2 and pypy compliant

Code:

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

回答 3

我认为您可以停在,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的所有除数。

资料来源:如何确定数字的除数

I think you can stop at math.sqrt(n) instead of n/2.

I will give you example so that you can understand it easily. Now the sqrt(28) is 5.29 so ceil(5.29) will be 6. So I if I will stop at 6 then I will can get all the divisors. How?

First see the code and then see image:

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

Now, See the image below:

Lets say I have already added 1 to my divisors list and I start with i=2 so

So at the end of all the iterations as I have added the quotient and the divisor to my list all the divisors of 28 are populated.

Source: How to determine the divisors of a number


回答 4

我喜欢Greg解决方案,但我希望它更像python。我觉得它会更快,更易读。所以经过一段时间的编码后,我想到了这一点。

要创建列表的笛卡尔积,需要前两个功能。一旦出现此问题,便可以重复使用。顺便说一下,我必须自己编写程序,如果有人知道该问题的标准解决方案,请随时与我联系。

现在,“ Factorgenerator”将返回一个字典。然后将字典放入“除数”中,后者使用字典首先生成一个列表列表,其中每个列表都是具有p素数的p ^ n形式的因子的列表。然后,我们生成这些列表的笛卡尔乘积,最后使用Greg的解决方案生成除数。我们对它们进行排序,然后将其退回。

我测试了它,它似乎比以前的版本要快一些。我将它作为一个更大的程序的一部分进行了测试,所以我不能真正说出它快多少。

彼得罗·斯佩罗尼(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。我期待任何反馈。

I like Greg solution, but I wish it was more python like. I feel it would be faster and more readable; so after some time of coding I came out with this.

The first two functions are needed to make the cartesian product of lists. And can be reused whnever this problem arises. By the way, I had to program this myself, if anyone knows of a standard solution for this problem, please feel free to contact me.

“Factorgenerator” now returns a dictionary. And then the dictionary is fed into “divisors”, who uses it to generate first a list of lists, where each list is the list of the factors of the form p^n with p prime. Then we make the cartesian product of those lists, and we finally use Greg’ solution to generate the divisor. We sort them, and return them.

I tested it and it seem to be a bit faster than the previous version. I tested it as part of a bigger program, so I can’t really say how much is it faster though.

Pietro Speroni (pietrosperoni dot it)

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)

P.S. it is the first time I am posting to stackoverflow. I am looking forward for any feedback.


回答 5

这是在纯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))

Here is a smart and fast way to do it for numbers up to and around 10**16 in pure 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))

回答 6

改编自CodeReview,这是一个与num=1!一起使用的变体!

from itertools import product
import operator

def prod(ls):
   return reduce(operator.mul, ls, 1)

def powered(factors, powers):
   return prod(f**p for (f,p) in zip(factors, powers))


def divisors(num) :

   pf = dict(prime_factors(num))
   primes = pf.keys()
   #For each prime, possible exponents
   exponents = [range(i+1) for i in pf.values()]
   return (powered(primes,es) for es in product(*exponents))

Adapted from CodeReview, here is a variant which works with num=1 !

from itertools import product
import operator

def prod(ls):
   return reduce(operator.mul, ls, 1)

def powered(factors, powers):
   return prod(f**p for (f,p) in zip(factors, powers))


def divisors(num) :

   pf = dict(prime_factors(num))
   primes = pf.keys()
   #For each prime, possible exponents
   exponents = [range(i+1) for i in pf.values()]
   return (powered(primes,es) for es in product(*exponents))

回答 7

我将添加一个稍微修改过的Anivarth版本(因为我认为它是最Python的)以供将来参考。

from math import sqrt

def divisors(n):
    divs = {1,n}
    for i in range(2,int(sqrt(n))+1):
        if n%i == 0:
            divs.update((i,n//i))
    return divs

I’m just going to add a slightly revised version of Anivarth’s (as I believe it’s the most pythonic) for future reference.

from math import sqrt

def divisors(n):
    divs = {1,n}
    for i in range(2,int(sqrt(n))+1):
        if n%i == 0:
            divs.update((i,n//i))
    return divs

回答 8

旧问题,但这是我的看法:

def divs(n, m):
    if m == 1: return [1]
    if n % m == 0: return [m] + divs(n, m - 1)
    return divs(n, m - 1)

您可以代理:

def divisorGenerator(n):
    for x in reversed(divs(n, n)):
        yield x

注意:对于支持的语言,这可能是尾递归。

Old question, but here is my take:

def divs(n, m):
    if m == 1: return [1]
    if n % m == 0: return [m] + divs(n, m - 1)
    return divs(n, m - 1)

You can proxy with:

def divisorGenerator(n):
    for x in reversed(divs(n, n)):
        yield x

NOTE: For languages that support, this could be tail recursive.


回答 9

假设factors函数返回n的因数(例如,factors(60)返回列表[2,2,3,5]),这是一个计算n除数的函数

function divisors(n)
    divs := [1]
    for fact in factors(n)
        temp := []
        for div in divs
            if fact * div not in divs
                append fact * div to temp
        divs := divs + temp
    return divs

Assuming that the factors function returns the factors of n (for instance, factors(60) returns the list [2, 2, 3, 5]), here is a function to compute the divisors of n:

function divisors(n)
    divs := [1]
    for fact in factors(n)
        temp := []
        for div in divs
            if fact * div not in divs
                append fact * div to temp
        divs := divs + temp
    return divs

回答 10

这是我的解决方案。它似乎很愚蠢,但效果很好…而且我试图找到所有合适的除数,所以循环从i = 2开始。

import math as m 

def findfac(n):
    faclist = [1]
    for i in range(2, int(m.sqrt(n) + 2)):
        if n%i == 0:
            if i not in faclist:
                faclist.append(i)
                if n/i not in faclist:
                    faclist.append(n/i)
    return facts

Here’s my solution. It seems to be dumb but works well…and I was trying to find all proper divisors so the loop started from i = 2.

import math as m 

def findfac(n):
    faclist = [1]
    for i in range(2, int(m.sqrt(n) + 2)):
        if n%i == 0:
            if i not in faclist:
                faclist.append(i)
                if n/i not in faclist:
                    faclist.append(n/i)
    return facts

回答 11

如果您只在乎使用列表推导,对您而言别无其他!

from itertools import combinations
from functools import reduce

def get_devisors(n):
    f = [f for f,e in list(factorGenerator(n)) for i in range(e)]
    fc = [x for l in range(len(f)+1) for x in combinations(f, l)]
    devisors = [1 if c==() else reduce((lambda x, y: x * y), c) for c in set(fc)]
    return sorted(devisors)

If you only care about using list comprehensions and nothing else matters to you!

from itertools import combinations
from functools import reduce

def get_devisors(n):
    f = [f for f,e in list(factorGenerator(n)) for i in range(e)]
    fc = [x for l in range(len(f)+1) for x in combinations(f, l)]
    devisors = [1 if c==() else reduce((lambda x, y: x * y), c) for c in set(fc)]
    return sorted(devisors)

回答 12

如果您的PC拥有大量内存,那么使用numpy可以使单个行足够快:

N = 10000000; tst = np.arange(1, N); tst[np.mod(N, tst) == 0]
Out: 
array([      1,       2,       4,       5,       8,      10,      16,
            20,      25,      32,      40,      50,      64,      80,
           100,     125,     128,     160,     200,     250,     320,
           400,     500,     625,     640,     800,    1000,    1250,
          1600,    2000,    2500,    3125,    3200,    4000,    5000,
          6250,    8000,   10000,   12500,   15625,   16000,   20000,
         25000,   31250,   40000,   50000,   62500,   78125,   80000,
        100000,  125000,  156250,  200000,  250000,  312500,  400000,
        500000,  625000, 1000000, 1250000, 2000000, 2500000, 5000000])

在我的慢速PC上花费不到1秒。

If your PC has tons of memory, a brute single line can be fast enough with numpy:

N = 10000000; tst = np.arange(1, N); tst[np.mod(N, tst) == 0]
Out: 
array([      1,       2,       4,       5,       8,      10,      16,
            20,      25,      32,      40,      50,      64,      80,
           100,     125,     128,     160,     200,     250,     320,
           400,     500,     625,     640,     800,    1000,    1250,
          1600,    2000,    2500,    3125,    3200,    4000,    5000,
          6250,    8000,   10000,   12500,   15625,   16000,   20000,
         25000,   31250,   40000,   50000,   62500,   78125,   80000,
        100000,  125000,  156250,  200000,  250000,  312500,  400000,
        500000,  625000, 1000000, 1250000, 2000000, 2500000, 5000000])

Takes less than 1s on my slow PC.


回答 13

我通过生成器函数的解决方案是:

def divisor(num):
    for x in range(1, num + 1):
        if num % x == 0:
            yield x
    while True:
        yield None

My solution via generator function is:

def divisor(num):
    for x in range(1, num + 1):
        if num % x == 0:
            yield x
    while True:
        yield None

回答 14

return [x for x in range(n+1) if n/x==int(n/x)]
return [x for x in range(n+1) if n/x==int(n/x)]

回答 15

对我来说,这很好,也很干净(Python 3)

def divisors(number):
    n = 1
    while(n<number):
        if(number%n==0):
            print(n)
        else:
            pass
        n += 1
    print(number)

速度不是很快,但是可以按需逐行返回除数,如果您确实想要,也可以执行list.append(n)和list.append(number)

For me this works fine and is also clean (Python 3)

def divisors(number):
    n = 1
    while(n<number):
        if(number%n==0):
            print(n)
        else:
            pass
        n += 1
    print(number)

Not very fast but returns divisors line by line as you wanted, also you can do list.append(n) and list.append(number) if you really want to