CODEWITHSUNDEEP
pythonpython-3.xmathprime-factoring
auden
auden

Reputation: 1157

Prime factorization code produces IndexError with certain numbers

Problem

When 32, and select other numbers are inputted, the following error is given:

Traceback (most recent call last):
  File "python", line 43, in <module>
IndexError: list assignment index out of range

(Line 43 is extrafactors[i] = factorCheck(i).) However, with other numbers, the code works just fine.

Code

from functools import reduce

n = int(input("Please input a whole number"))
primes = []

def isPrime(x):
    if x<2:
        return False
    for i in range(2,x):
        if not x%i:
           return False
    return True 

def factorCheck(n):
    x = []
    for i in range(1,n):
        if n%i==0:
            x.append(i)
        return x

if isPrime(n) == True:
    print("1, ",n)
else:
    for i in range (1,n):
        if isPrime(i) == True:
            if n%i == 0:
                primes.append(i)
    multiplied = reduce(lambda x, y: x*y, primes)
    if multiplied != n:
        left = int(n/multiplied)
        if isPrime(left) == True:
            primes.append(left)
        else:
            extrafactors = []
            extrafactors = factorCheck(left)
            while len(extrafactors) > 0:
                for i in extrafactors:
                    if isPrime(i) == True:
                        primes.append(i)
                        extrafactors.remove(i)
                    else:
                        extrafactors[i] = factorCheck(i)
                        extrafactors = [item for sublist in extrafactors for item in sublist]
    primes = sorted(primes)
    print(primes)

Code Explanation

There are two functions defined. One checks if a number is prime, and the other produces a list of factors of a number. First, the program takes in the number inputted by the user. Then, it tests if it is prime, and prints the prime factorization then (1, whatever the number is). If it isn't, it basically finds all primes that are factors of the number and are also prime. The program then multiplies these together, and if they are less than the original number inputted, it finds (prime) factors of the difference and appends them to the list of prime numbers which is printed at the end.

I understand the program may be inefficient, but I understand it how it is written. The line that gives the error replaces a number with a list of factors of that number.

Upvotes: 0

Views: 75

Answers (2)

Neil
Neil

Reputation: 14321

This problem is easier to do with a recursive function. Recursive functions call themselves. So, basically once we find a factor, we check to see if the number can be factored further, if it can be we append it to the list and keep factoring, if it can't be factored, then we simply append and return.

def factor(numberToFactor, arr=list()):
    for i in range(2, numberToFactor // 2 + 1):
        if numberToFactor % i == 0:
            return factor(numberToFactor/i,arr + [i])
    return list(set(arr + [numberToFactor]))

print(factor(32))

Upvotes: 1

user448810
user448810

Reputation: 17866

I'm not going to review your code. It's much more complicated than it needs to be.

Here is a simple function for factoring integers. It's not the best way to factor integers, but it's simple and reasonably efficient as long as n isn't too big, less than a dozen digits, say.

def factors(n):
    f, fs = 2, []
    while f * f <= n:
        if n % f == 0:
            fs.append(f)
            n = n / f
        else:
            f = f + 1
    fs.append(n)
    return fs

Upvotes: 2

Related Questions