0

任意の数nの素因数を見つけるプログラムがあります。実行すると、インデックスが制限を超えているため（制限はsqrt（n））、インデックスエラーが発生します。なぜ制限を超えているのかわかりません。誰かが洞察を提供できますか？

私のコードはほとんどの数字でうまく機能します：

>>> pFactors(250000)
[2, 2, 2, 2, 5, 5, 5, 5, 5, 5]
>>> pFactors(123456789)
[3, 3, 3607, 3803]
>>> pFactors(123456)

Traceback (most recent call last):
  File "<pyshell#2>", line 1, in <module>
    pFactors(123456)
  File "D:\my_stuff\Google Drive\Modules\factors.py", line 50, in pFactors
    check = primes[index]
IndexError: list index out of range
>>> pFactors(123455)

Traceback (most recent call last):
  File "<pyshell#3>", line 1, in <module>
    pFactors(123455)
  File "D:\my_stuff\Google Drive\Modules\factors.py", line 50, in pFactors
    check = primes[index]
IndexError: list index out of range

奇妙なことに、これまでのところ、123400〜1234の番号では機能しないことがわかりました。

これが私のコードです：

def pFactors(n):
   import primes as p
   from math import sqrt
   global pFact
   pFact, primes, limit, check, num, index = [], [], int(round(sqrt(n))), 2, n, 0
   if type(n) != int and type(n) != long:
      raise TypeError("Argument <n> can only be <type 'int'> or <type 'long'>")
   else:
      if p.isPrime(n):
         pFact = [1, n]
      else:
         p.prevPrimes(limit)
         for i in p.primes_dict:
            if p.primes_dict[i]:
               primes.append(i)
         while check <= limit:
            if check in primes and (num%check==0):
               pFact.append(check)
               num = num / check
               if num in primes:
                  pFact.append(num)
                  break
            else:
               check = primes[index]
               index += 1
      return pFact

これは問題なく機能するので、問題はにあるのではないと確信していますprimes.py。誰かがこれを修正する方法について何か解決策を持っているなら、私に教えてください。ありがとう！

4

1 に答える 1

2

平方根の天井をリストの長さとして使用したいのですが、それを丸めているだけなので、切り捨てられることがあります。

さらに良いことに、の代わりにintベースの平方根関数を使用して、doublemath.sqrtに対して大きすぎる数値に対しても機能するようにします。

また、global pFactひどいデザインです。あなたがそれか何かをデバッグしようとしているのでない限り、これにグローバルリストを使用する理由はまったくありません、そしてそれでもそれは疑わしいです。

最後に、素数の場合、なぜ1を因数として返したいのかわかりません。これは慣例に反しており、複合ケースと矛盾していますが、本当に必要な場合は、そのように行うことができると思います。

とにかく、これが因数分解を行う簡単な方法です。そもそも機能するようになったら、最適化について心配することができます。

def factor(x):
    n = int(x)
    if n < 1:
        raise ValueError("Argument must be positive")

    factors = []
    d = 2

    while d*d <= n:
        while n%d == 0:
            n = n // d
            factors.append(d)
        d += 1
    if n>1:
        factors.append(n)
    return factors
于 2012-11-26T17:00:58.160 に答える