15

私は整数の因数分解を必要とするプロジェクトオイラー問題に取り組んでいます。与えられた数の因数であるすべての素数のリストを思いつくことができます。算術の基本定理は、このリストを使用して、数のすべての要素を導き出すことができることを意味します。

私の現在の計画は、基本素数のリストの各数値を取得し、各素数の最大指数を見つけるための素因数がなくなるまでその累乗を上げることです。次に、素数と指数のペアの可能なすべての組み合わせを乗算します。

たとえば、180の場合：

Given: prime factors of 180: [2, 3, 5]
Find maximum exponent of each  factor: 
    180 / 2^1 = 90
    180 / 2^2 = 45
    180 / 2^3 = 22.5 - not an integer, so 2 is the maximum exponent of 2.

    180 / 3^1 = 60
    180 / 3^2 = 20
    180 / 3^3 = 6.6 - not an integer, so 2 is the maximum exponent of 3.

    180 / 5^1 = 36
    180 / 5^2 = 7.2 - not an integer, so 1 is the maximum exponent of 5.

次に、これらのすべての組み合わせを最大指数まで実行して、係数を取得します。

    2^0 * 3^0 * 5^0 = 1
    2^1 * 3^0 * 5^0 = 2
    2^2 * 3^0 * 5^0 = 4
    2^0 * 3^1 * 5^0 = 3
    2^1 * 3^1 * 5^0 = 6
    2^2 * 3^1 * 5^0 = 12
    2^0 * 3^2 * 5^0 = 9
    2^1 * 3^2 * 5^0 = 18
    2^2 * 3^2 * 5^0 = 36
    2^0 * 3^0 * 5^1 = 5
    2^1 * 3^0 * 5^1 = 10
    2^2 * 3^0 * 5^1 = 20
    2^0 * 3^1 * 5^1 = 15
    2^1 * 3^1 * 5^1 = 30
    2^2 * 3^1 * 5^1 = 60
    2^0 * 3^2 * 5^1 = 45
    2^1 * 3^2 * 5^1 = 90
    2^2 * 3^2 * 5^1 = 180

したがって、要因のリスト= [1、2、3、4、5、6、9、10、12、15、18、20、30、36、45、60、90、180]

これが私がこれまでに持っているコードです。2つの問題：最初に、それはまったくPythonicではないと思います。それを直したいのですが。第二に、私には、組み合わせの2番目のステップを実行するためのPythonの方法が本当にありません。恥ずかしさから、私はあなたをばかげたループのセットから免れました。

nは因数分解したい数です。listOfAllPrimesは、1,000万までの素数の事前計算されたリストです。

def getListOfFactors(n, listOfAllPrimes):
    maxFactor = int(math.sqrt(n)) + 1
    eligiblePrimes = filter(lambda x: x <= maxFactor, listOfAllPrimes)
    listOfBasePrimes = filter(lambda x: n % x ==0, eligiblePrimes)

    listOfExponents = [] #(do I have to do this?)
    for x in listOfBasePrimes:
        y = 1
        while (x**(y+1)) % n == 0:
            y += 1
        listOfExponents.append(y)
4

6 に答える 6

11

指数のリストの代わりに、各素因数を因子である回数だけ繰り返すことを検討してください。その後、結果の繰り返し付きリストで作業することで、itertools.combinationsは必要なことを実行します。必要なのは、含まれるアイテムの長さ2の組み合わせだけです（1つだけの組み合わせが主な要因であり、すべての組み合わせです。それらのうちの元の番号になります-それらも必要な場合は、私の主な提案が使用するものの代わりに使用してください）。primefactorslen(primefactors) - 1range(1, len(primefactors) + 1)range(2, len(primefactors))

結果には繰り返しがあり（たとえば、後者はのようになるため、6の係数として2回表示されます）、もちろん通常の方法で（たとえば）取り除くことができます。12primefactors[2, 2, 3]sorted(set(results))

primefactors与えられたものを計算するlistOfAllPrimesには、たとえば次のことを考慮してください。

def getprimefactors(n):
    primefactors = []
    primeind = 0
    p = listOfAllPrimes[primeind]
    while p <= n:
        if n % p == 0:
            primefactors.append(p)
            n //= p
        else:
            primeind += 1
            p = listOfAllPrimes[primeind]
    return primefactors
于 2010-09-04T19:46:30.987 に答える
6

なぜ一連の素因数からソリューションを開始するのですか？数を因数分解すると、そのすべての素因数（繰り返し）を簡単に取得でき、それらから各素因数の指数を取得できます。これを念頭に置いて、次のように書くことができます。

import itertools
prime_factors = get_prime_factors(180) 
# 2, 2, 3, 3, 5 
factorization = [(f, len(list(fs))) for (f, fs) in itertools.groupby(prime_factors)]
# [(2, 2), (3, 2), (5, 1)]
values = [[(factor**e) for e in range(exp+1)] for (factor, exp) in factorization]
# [[1, 2, 4], [1, 3, 9], [1, 5]]
print sorted(product(xs) for xs in itertools.product(*values))
# [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180]

get_prime_factorsここでproductは実装されていませんが、アイデアは得られます（どちらも非常に簡単に記述できます）

IMHOは数学の問題であるため、オイラーの問題は命令型ではなく関数型を使用してうまく解決できます（ただし、一部の解決策は希望どおりにpythonicで表示されない場合があることを認識しています）。

于 2010-09-04T22:53:29.980 に答える
3

のようにitertools.combinations()、繰り返される素数のリストを取得したら、を使用して、可能なすべての要素の組み合わせを取得できます。次に、各組み合わせのコンポーネントを単純に乗算すると、係数が得られます。[2, 2, 3, 3, 5]180

于 2010-09-04T19:48:10.187 に答える
2

いくつかのよりクールなPython機能：

def factors( num ):
    for p in primes:
        if num==1: break # stop when num is 1
        while True: # these factors may be repeated 
            new, rest = divmod(num, p) # does div and mod at once
            if rest==0: # its divisible
                yield p # current prime is factor
                num = new # continue with the div'd number
            else:
                break # no factor so break from the while


print list(factors(2*2*3*3*5*7*11*11*13)) # [2, 2, 3, 3, 5, 7, 11, 11, 13] ofc
于 2010-09-04T22:55:12.223 に答える
1

元の問題に対する簡単で効率的な解決策は次のとおりです。

def getDivisors(n):
    divisors = []
    d = 1
    while d*d < n:
        if n % d == 0:
            divisors.append(d)
            divisors.append(n / d);
        d += 1
    if d*d == n:
        divisors.append(d)
    return divisors

出力リストはソートされていません。必要に応じて、それが何を意味するかにかかわらず、より「pythonic」にすることができます。

于 2010-09-04T21:27:06.703 に答える
1

オールインワンソリューション。つまり、素因数の既存のリストは必要ありません。

#!/usr/bin/python3 -O

from primegen import erat3 as generate_primes # see Note[1]
import operator as op, functools as ft, itertools as it

def all_factors(number):
    prime_powers= []

    for prime in generate_primes(): # for prime in listOfAllPrimes
        if prime > number: break

        this_prime_powers= [1]
        new_number, modulo= divmod(number, prime)

        while not modulo:
            number= new_number
            this_prime_powers.append(this_prime_powers[-1] * prime)
            new_number, modulo= divmod(number, prime)

        if len(this_prime_powers) > 1:
            prime_powers.append(this_prime_powers)

    # at this point:
    # if number was 360, prime_powers is [[1, 2, 4, 8], [1, 3, 9], [1, 5]]
    # if number was 210, prime_powers is [[1, 2], [1, 3], [1, 5], [1, 7]]

    return sorted(
        ft.reduce(op.mul, combination, 1)
        for combination in it.product(*prime_powers))

if __name__ == "__main__":
    def num_result(number):
        return number, all_factors(number)
    print(num_result(360))
    print(num_result(210))
    print(num_result(7))

注[1] ：素数ジェネレーターとして、Pythonで素数の効率的な無限ジェネレーターを実装する方法から1つを選択できますか？または独自のものを使用します（例：your listOfAllPrimes）。

これにより、完全な因子リストが生成されます。つまり1、number引数自体が含まれます。これらを省略したい場合は、を使用できますall_factors(number)[1:-1]。

$ allfactors.py 
(360, [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360])
(210, [1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210])
(7, [1, 7])
于 2010-10-04T12:19:15.967 に答える