0

nの素因数分解を見つけるプログラムを書こうとしています！。私は以前にこれを成功させましたが、すでに書いたコードが見つからないので、書き直さなければなりません！：pここにコードがあります： 

import math                                                                                                                                                 
import numpy as np
import itertools as it
import operator as op

def primes(n):
    """A simple sieve to find the primes less than n"""                                                                                                                                              
    nums = np.arange(3,n+1,2)                                                                                                                               
    sqrtn = int(n**0.5)/2                                                                                                                                   
    for step in nums[:sqrtn]:                                                                                                                               
        if step:
            nums[step*step/2-1::step]=0
    return [2] + map(int, filter(None, nums))

def factFactors(n):
    """Finds the prime factorization of n! using the property found
    here: http://en.wikipedia.org/wiki/Factorial#Number_theory"""                                                                               
    ps = primes(n)                                                                                                                                        
    for p in ps:                                                                                                                             
        e = 0                                                                                                                                               
        for i in it.count(1):                                                                                                                                
            epeice = n/(p**i)                                                                                                                               
            if epeice == 0: break
            e += epeice                                                                                                                                     
        yield p, e                                                                                                                                               

if __name__=="__main__":
    x = list(factFactors(100))
    print x, reduce(op.mul, [p**e for p, e in x], 1)==math.factorial(100)

出力は次のとおりです。

[(2, 97), (3, 48), (5, 24), (7, 16), (11, 9), (13, 7), (17, 5), (19, 5), (23, 4), (29, 3), (31, 3), (37, 2), (41, 2), (43, 2), (47, 2), (53, 1), (59, 1), (6
1, 1), (67, 1), (71, 1), (73, 1), (79, 1), (83, 1), (89, 1), (97, 1)] False

私はこれを何時間も見てきましたが、何が悪いのかわかりません...

4

1 に答える 1

1

このコードは、実験中に何度も変更されましたが、現在のバージョンの問題の 1 つfactFactorsは、ジェネレーターであるため、

x = factFactors(100)                                       
print list(x), reduce(op.mul, [p**e for p, e in x], 1)==math.factorial(100)

を呼び出すlistとジェネレーターreduceが使い果たされるため、何もする必要がありません。x = list(factFactors(100))代わりに使用してください。

-

result/のタイプミスを修正した後results(まあ、これを書き始めたときに存在していたものです!)、コードを実行できません。

~/coding$ python2.7 factbug4.py
factbug4.py:31: RuntimeWarning: overflow encountered in long_scalars
  print x, reduce(lambda a, b: a*b, [p**e for p, e in x], 1)==math.factorial(100)
[(2, 97), (3, 48), (5, 24), (7, 16), (11, 9), (13, 7), (17, 5), (19, 5), (23, 4), (29, 3), (31, 3), (37, 2), (41, 2), (43, 2), (47, 2), (53, 1), (59, 1), (61, 1), (67, 1), (71, 1), (73, 1), (79, 1), (83, 1), (89, 1), (97, 1)]
Traceback (most recent call last):
  File "factbug4.py", line 31, in <module>
    print x, reduce(lambda a, b: a*b, [p**e for p, e in x], 1)==math.factorial(100)
  File "factbug4.py", line 31, in <lambda>
    print x, reduce(lambda a, b: a*b, [p**e for p, e in x], 1)==math.factorial(100)
TypeError: unsupported operand type(s) for *: 'long' and 'numpy.int32'

しかし、それはおそらく問題が何であるかを示唆しています。(コードは私には実行されないので、確信は持てませんが、合理的に確信しています。) によって返される要素のほとんどは、primesPython の任意精度の整数ではなく、制限された範囲の numpy 整数です。

>>> primes(10)
[2, 3, 5, 7]
>>> map(type, primes(10))
[<type 'int'>, <type 'numpy.int32'>, <type 'numpy.int32'>, <type 'numpy.int32'>]

それらに対する操作はオーバーフローする可能性があります。と を変換するpと:eint

print x, reduce(lambda a, b: a*b, [int(p)**int(e) for p, e in x], 1)==math.factorial(100)

私は得る

[(2, 97), (3, 48), (5, 24), (7, 16), (11, 9), (13, 7), 
(17, 5), (19, 5), (23, 4), (29, 3), (31, 3), (37, 2), 
(41, 2), (43, 2), (47, 2), (53, 1), (59, 1), (61, 1), 
(67, 1), (71, 1), (73, 1), (79, 1), (83, 1), (89, 1), (97, 1)] True

任意の精度での配列インデックス付けの利便性が必要な場合は、numpydtype of を使用できます。object

>>> np.arange(10,dtype=object)
array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], dtype=object)

しかし、正直なところ、numpyここではまったく使用しないことをお勧めします。

于 2013-03-19T18:28:42.837 に答える