Python: finding the +100th prime number

Question

I have a weird problem with my program. When n<=100 it works just fine. However when it comes to bigger numbers(such as n=121) it keeps showing me this message:

File "my_code.py2", line 24, in 
    print k[int(n)]
IndexError: list index out of range

Code:

k=[]
z=[]
a=0
k.append(1)
k.append(2)
k.append(3)
n=raw_input()
while n!="END" and int(n)>0 and int(n)%100000==int(n):              
    for x in xrange(3,7919,2): 
        for i in xrange(3,x,2):      
            if x%i!=0:
                a=1
            else:
                a=0
                break
        if a==1:
            k.append(x)
        if len(k)==int(n):
            break          
    print k[int(n)]
    n=raw_input()

Can you help me???

Answer 1

I think you have an off-by-one error. Python uses zero based-indexing, so to get the 121st element you would want to access your list at k[120].

By the way, 1 is not a prime number.

---

edit: Rather than fix up other issues with the code that you've mention in the comments, might I suggest a better algorithm? Rather than checking for divisors, the sieve of eratosthenes is the usual way of listing all primes below a bound. It's easy to implement and should be faster than your current method with nested loops.

Answer 2

This is because you break the loop when len(k) == int(n) and then access k[int(n)]. Since python uses 0 based indexing, when the list length is equal to n, the last index you can access is n-1.

As you add 1 to the list, and 1 is not a prime, every other prime in the list will have their actual index.

I.e 2 is at index 1, and 2 is the first prime. 3 is at index 2, and 3 is the second prime.

So, the solution is to change len(k) == int(n) to len(k) == int(n) + 1.

NOTE: There is an another issue with your program. When ever the statements inside the outer loop get excuted. It keeps adding elements to k unnecessarily. So, what i suggest is first calculate all the primes upto a certain limit. And then just query that list. Don't repeatedly calculate all the primes from the beginning.

k=[]
z=[]
a=0

k.append(1)
k.append(2)
k.append(3)

for x in xrange(3,7919,2): 
    for i in xrange(3,x,2):      
        if x%i!=0:
            a=1
        else:
            a=0
            break
    if a==1:
        k.append(x)

n = raw_input()
while n!="END" and int(n)>0 and int(n) < len(k):                      
    print k[int(n)]
    n = raw_input()