1

数をその因数の積として表現したい。数を表すために使用される因数の数は、2から同じ数の素数の数でなければなりません（これは、数の因子の可能な最大数です） 。

たとえば、24という数字を取ります。

2つの因子の乗算としての数の表現は、、など2*12です8*3... 6*4、

3つの因子の乗算としての数の表現は2*2*6、2*3*4などです...、

4つの因子の乗算（素因数のみ）としての数の表現は2*2*2*3です。

このためのいくつかの単純で一般的なアルゴリズムを取得するのを手伝ってください

4

3 に答える 3

2

これにより、乗算して元の数を与えるすべての因数セットが生成されます。すべての製品セットを、並べ替えられたタプルの一意のリストとして返します。

s は、1無限再帰を避けるために除外されます。

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

def product_sets(n):
    return set(products(1, [], n, prime_factors(n)))



def products(current_product, current_list, aim, factors):

    if current_product == aim:
        yield tuple(sorted(current_list))

    elif 0 < current_product < aim:
        for factor in factors:
            if factor != 1:
                for product in products(current_product * factor, current_list + [factor], aim, factors):
                    yield product


print list(product_sets(24))

出力：

[(4, 6), (3, 8), (2, 12), (2, 3, 4), (24,), (2, 2, 6), (2, 2, 2, 3)]
于 2013-02-25T14:46:56.597 に答える
0

次の関数は、指定された数値 のすべての因数を返しますn。特定のペアではなく、すべての要素を返すことに注意してください。

def factors(n):
    """Finds all the factors of 'n'"""
    fList, num, y, limit = [], n, 0, int(sqrt(n)) + 1
    for factor in range(1, limit):
        if n % factor == 0:
            if factor not in fList: fList.append(factor)
            y = n / factor
            if y not in fList: fList.append(y)
    return sorted(fList)

たとえば、factors(24)次のとおりです。

>>> factors(24)
[1, 2, 3, 4, 6, 8, 12, 24]
于 2013-02-25T14:31:22.520 に答える
0

私は1つ知っています...

Pythonを使用している場合は、辞書を使用してストレージを簡素化できます...

数の平方根未満のすべての素数を確認する必要があります。

ここで、p^k があなたの数 n を割るとします。あなたの仕事は、k を見つけることだと思います。メソッドは次のとおりです。

int c = 0; int temp = n; while(temp!=0) { temp /= p; c+= 温度; }

上記は C++ のコードですが、お分かりいただけると思います... このループの最後には c = k となります。

そして、そうです、willによって与えられたリンクは、同じアルゴリズムの完璧なpython実装です

于 2013-02-25T14:06:20.540 に答える