python - 数の約数をすべて取得するための最良の方法は何ですか？

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

これを出力します：

更新： Greg Hewgillと彼の「スマートな方法」に感謝します:)100000000のすべての除数を計算するのに、私のマシンでの馬鹿げた方法が取った39に対して、0.01秒かかりました。非常にクールです：D

更新2：これはこの投稿の複製であると言うのをやめます。特定の数の約数を計算するために、すべての約数を計算する必要はありません。ウィキペディアで「除数関数」を探していない場合は、別の問題です。投稿する前に質問と回答を読んでください。トピックが何であるかがわからない場合は、役に立たない回答を追加しないでください。

score 81 · Accepted Answer

あなたの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。

score 39 · Accepted Answer

シミが言ったことを拡張するには、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]

score 25 · Accepted Answer

math.sqrt(n)n/2 の代わりに停止できると思います。

わかりやすいように例を出します。これで 6 になります。6 で止めれば、すべての約数を得ることができsqrt(28)ます5.29。ceil(5.29)どのように？

最初にコードを見て、次に画像を見てください：

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 のすべての除数が入力されます。

出典:数値の約数を決定する方法

score 8 · Accepted Answer

私はグレッグのソリューションが好きですが、それがもっと Python に似ていたらいいのにと思います。より速く、より読みやすくなると思います。そのため、しばらくコーディングした後、これを思いつきました。

最初の 2 つの関数は、リストのデカルト積を作成するために必要です。この問題が発生した場合はいつでも再利用できます。ところで、私はこれを自分でプログラムしなければなりませんでした。誰かがこの問題の標準的な解決策を知っているなら、私に連絡してください。

"Factorgenerator" は辞書を返すようになりました。そして、ディクショナリは "divisors" に入力され、最初にそれを使用してリストのリストが生成されます。ここで、各リストは p^n の形式の因子のリストであり、素数が p です。次に、これらのリストのデカルト積を作成し、最後に Greg の解を使用して除数を生成します。仕分けしてお返しします。

テストしたところ、以前のバージョンよりも少し速いようです。私はより大きなプログラムの一部としてテストしたので、どれだけ速いかはわかりません.

Pietro Speroni（ピエトロスペローニドットイット）

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スタックオーバーフローに投稿するのは初めてです。フィードバックをお待ちしております。

score 2 · Accepted Answer

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

score 1 · Accepted Answer

古い質問ですが、ここに私の見解があります：

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

注: サポートする言語の場合、これは末尾再帰になる可能性があります。

score 0 · Accepted Answer

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

score 0 · Accepted Answer

これが私の解決策です。ばかげているようですが、うまく機能します...そして、適切な除数をすべて見つけようとしていたので、ループは 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

score -1 · Accepted Answer

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

score -1 · Accepted Answer

-1

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

于 2014-06-01T19:20:42.763 に答える

python - 数の約数をすべて取得するための最良の方法は何ですか？

19 に答える 19

Related

Reference