数の主要な要因のPythonリストがあります。すべての要因を（pythonicで）見つけるにはどうすればよいですか？
https://stackoverflow.com/questions/3643725
-
30-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
整数の因数分解を必要とするプロジェクトオイラーの問題に取り組んでいます。特定の数の要因であるすべての素数のリストを思いつくことができます。算術の基本的な定理は、私がこのリストを使用して導き出すことができることを意味します 毎日 数の要因。
私の現在の計画は、各プライムのリストに各番号を取得し、各プライムの最大指数を見つけるための整数因子になるまでその力を上げることです。次に、プライムエクセンペンペアのすべての可能な組み合わせを掛けます。
たとえば、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つの問題：最初に、私はそれがまったくピトニックであるとは思わない。修正したいのですが。第二に、i 本当 組み合わせの2番目のステップを実行するためのPythonicの方法はありません。恥ずかしく、私はあなたをばかげたループのセットからあなたをspareしみました。
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)
解決
指数のリストの代わりに、簡単に考慮してください 繰り返し それぞれのプライムファクターはそれを回数ぶりに は 要因。その後、結果に取り組んでいます primefactors リスト付きのリスト、 itertools.combinations 必要なことだけを行います - 長さ2の組み合わせが必要です len(primefactors) - 1 含まれるアイテム（1つだけの組み合わせが主要な要因であり、それらのすべてが元の数字になります - あなたもそれらを望むなら、ただ使用するだけです range(1, len(primefactors) + 1) の代わりに range(2, len(primefactors)) 私の主な提案が使用するもの）。
結果には繰り返しがあります（例： 6 の要因として2回表示されます 12, 、後者から primefactors そうなるでしょう [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
他のヒント
一連のプライムファクターからソリューションを開始するのはなぜですか？数値を考慮すると、すべての主要な要因（繰り返される）を簡単に取得でき、そこから各要因の指数を取得できます。これを念頭に置いて、あなたはこれを書くことができます：
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 ここでは実装されていませんが、アイデアが得られます（両方とも非常に簡単に書くことができます）
私見は、数学的な問題であるため、オイラーの問題は、命令的なスタイルではなく機能的なものを使用してうまく解決できます（ただし、一部のソリューションは望ましいようにpythonicとして出てこないかもしれないことを認めています）。
使用できます itertools.combinations() 要因のすべての組み合わせを取得するには、繰り返しプリムのリストを取得したら、 [2, 2, 3, 3, 5] 為に 180. 。次に、各組み合わせからコンポーネントを掛けるだけで要因が得られます。
いくつかのクーラー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
元の問題に対するシンプルで効率的な解決策は次のとおりです。
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」にすることができます。
All in Oneソリューション。つまり、主要な要因の既存のリストは必要ありません。
#!/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: ：プライムナンバージェネレーターとして、から1つを選択できます Pythonで素数の効率的な無限発電機を実装する方法は？ またはあなた自身を使用します（例： 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])
