CODEWITHSUNDEEP
pythonlistindexing
Rushy Panchal
Rushy Panchal

Reputation: 17542

IndexError: list index out of range--- Prime Factor Generator

I have a program that finds the prime factors of any number, n. When running it, I get an index error because the index is exceeding the limit (where the limit is sqrt(n)). I'm not sure why it exceeds the limit. Can anyone provide any insight?

My code works well for most numbers: 

>>> 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

Oddly, so far I've only found it unable to work for numbers 123400-1234

Here is my code: 

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

I am sure that the problem doesn't lie in the primes.py, as this works fine. If anyone has any solutions on how to fix this, please tell me. Thanks!

Upvotes: 0

Views: 234

Answers (1)

Antimony
Antimony

Reputation: 39451

You want to use the ceiling of the square root as the list length, but you're just rounding it, which means it is sometimes rounded down.

Better yet, use an int based square root function instead of math.sqrt, so that it will work for numbers too large for doubles as well.

Also, global pFact is terrible design. There's no reason at all to use a global list for this, unless you're trying to debug it or something, and even then it's questionable.

Lastly, I'm not sure why you want to return 1 as a factor in the case of primes. It's against convention and inconsistent with your composite case, but I guess you could do it that way if you really want to.

Anyway, here's a simple way to do factoring. You can worry about optimizing it once you've got it working in the first place.

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

Upvotes: 2

Related Questions