2

I was trying to make a program which would check a number for its greatest prime factor. I was almost done when this error message came up. list index out of range.

What does this mean and what is wrong with my code?

Here is my code.

def is_prime(n):
    for i in range(3, n):
        if n % i == 0:
            return False
    return True

def Problem3():
    x = 144
    n = 2
    not_a_factor = []
    z = []
    prime = []
    not_a_prime = []
    while n < x:
        if x%n == 0:
            z.append(n)
        else:
            not_a_factor.append(n)
        n = n + 1
    for i in z:
        if is_prime(z[i]) == True:
            prime.append(z[i])
        else:
            not_a_prime.append(z[i])
    print(prime)
Problem3()
Daniel
  • 2,345
  • 4
  • 19
  • 36
smid_the_best
  • 95
  • 9
  • A full traceback would be helpful. The error means you're calling an item from a list that doesn't exist. If a list `my_list` has 3 items, and you call `my_list[3]` or greater (0 base index) you'll get that error. – Leb Mar 23 '16 at 02:14
  • You might want to go backwards in your first loop. If you're looking for greatest prime factor, start from the top and go down, checking for divisibility as well as primality. You can stop earlier, and won't have to build the list(s) of factors. – aghast Mar 23 '16 at 02:19

2 Answers2

0

You're just a bit off. for-loops in Python iterate an object and return it's entities, not a pointer/ index.

So just use the thing you get from each iteration of 'z'

(Side note: might want to check out this post, it'll help you make your is_prime function more performant)

def is_prime(n):
    for i in range(3, n):
        if n % i == 0:
            return False
    return True

def Problem3():
    x = 144
    n = 2
    not_a_factor = []
    z = []
    prime = []
    not_a_prime = []
    while n < x:
        if x%n == 0:
            z.append(n)
        else:
            not_a_factor.append(n)
        n =+ 1    # Python version of n++
    for i in z:   # Python for-loop is more like a say "for each", no need for the indexing
        if is_prime(i):  # no need for '=='; Python will 'truthify' your object
            prime.append(i)
        else:
            not_a_prime.append(i)
    print(prime)
Problem3()
Community
  • 1
  • 1
willnx
  • 1,253
  • 1
  • 8
  • 14
0

"list index out of range - what does this mean?"

The message list index out of range refers to an IndexError. Basically, this means that you are attempting to refer to an index in a list that doesn't exist.

Using your code as an example: you generate a list, z, containing the factors of the number 144. You then iterate through each element in this list (for i in z:). This means that for the:

  • 1st iteration: i is the 1st element in z, which is 2;
  • 2nd iteration: i is the 2nd element in z, which is 3;
  • and so on.

Then, you attempt if isprime(z[i]) == True:. So, as written, your program works like this:

  • 1st iteration: if isprime(z[2]) == True:;
  • 2nd iteration: if isprime(z[3]) == True:;
  • ...
  • 8th iteration: if isprime(z[16]) == True:

At this point, your code prompts an IndexError, because there are only 13 elements in z.

"what is wrong with my code?"

One way to get the result that you want is to iterate through range(len(z)) instead of each element of z. So, adjust the line for i in z to for i in range(len(z)).

Additionally, since prime is a list, and you want to return the greatest prime factor, change print(prime) to print(max(prime)).

These two changes will give you the result you are looking for.

Additional Learnings

Overall, your program could be written much more efficiently. If you want a simple algorithm to determine the greatest prime factor of a number, here is one possibility:

def greatest_prime_factor(n):
    greatest_prime = 1
    
    for i in range(n + 1):
        # iterate through range(n).  We skip index 0.
        if i == 0:
            continue
        
        # determine if the number i is a factor of n.
        if n % i == 0:
        
            # determine if the number i is prime.
            for i_ in range(2,i):
                if i % i_ == 0:
                    break
            else:
                # update greatest_prime.
                greatest_prime = max(greatest_prime, i)
    
    return greatest_prime
    
print (greatest_prime_factor(144))

This algorithm saves a lot of memory space when compared with your original program by not initializing lists to store numbers that are primes, that aren't primes, etc. If you want to store those values, that's up to you; there are just far more efficient possibilities for what you appear to want to achieve.

Check this link for some more info on algorithmic efficiency and how to think about time and space complexity.

Community
  • 1
  • 1
Daniel
  • 2,345
  • 4
  • 19
  • 36