Python 3: List of over 100 indices cycles back around after index 47. why? how do I stop this?

114 views Asked by At

so this is a function that gets the nth prime number. I know its been done before and that my method may not be very efficient (new coder btw minor dabbling in the past). Anyway the code below works and returns the prime number of the supplied index. ie:

ind = 4
final[1,2,3,5,7,11]
return final[ind-1]
returns: 5

But final[51-1] returns whats in final[3-1]. Seems like after index 47 it loops back around and starts over. Ive printed the whole of the list contained in final. and it prints every prime, even those past 47. Im not sure whats going on. Is there some limit to lists in python?

Here is the code:

def nthPrime(ind): #gets nth prime number. IE: 5th prime == 11. works based off very in-efficient version of Sieve of Eratosthenes. but in increments of 200
    p = {}
    T = 2
    incST = 2
    incEND = incST + 200
    final=[1]

    while len(final) < ind:
        for i in range(incST,incEND):
            p[i] = True

        while T <= math.sqrt(incEND):
            l = 0
            while l <= incEND:
                p[T**2 + (T*l)] = False
                l+=1
                if T**2+(T*l) > incEND:
                   break

            for k,v in p.items():
                if p[k] == True and k > T:
                    T = int(k)
                    break

        for k in p:
            if p[k] == True:
                final.append(k)

        incST = incEND + 1
        incEND = incST + 200

    '''
    currently function works perfectly for
    any index under 48.
    at index 48 and above it seems to start
    back at index 1.
    IE: final[51]
    ^would actually return final[4]
    '''


    return final[ind-1]
3

There are 3 answers

8
Jean-François Fabre On BEST ANSWER

You need to count how many primes you have in your list, but you accumulate in final within the loop, so you add all the numbers up to the limit several times in the loop. Starts at 2 again after 199.

Also, using dictionaries and relying on the order is dangerous. You should sort them when iterating.

My solution only counts the primes to know when to end the loop, and compose the list just in the end, omitting 1 and shifting the index by 1.

I also sort the dictionary when iterating over it to make sure:

import math

def nthPrime(ind): #gets nth prime number. IE: 5th prime == 11. works based off very in-efficient version of Sieve of Eratosthenes. but in increments of 200
    p = {}
    T = 2
    incST = 2
    incEND = incST + 200

    lenfinal = 1
    while lenfinal < ind:
        for i in range(incST,incEND):
            p[i] = True

        while T <= math.sqrt(incEND):
            l = 0
            while l <= incEND:
                p[T**2 + (T*l)] = False
                l+=1
                if T**2+(T*l) > incEND:
                   break

            for k,v in sorted(p.items()):
                if v and k > T:
                    T = int(k)
                    break


        incST = incEND + 1
        incEND = incST + 200
        # compute length, no need to order or to actually create the list
        lenfinal = sum(1 for k,v in p.items() if v)

    # now compose the list
    final = [k for k,v in sorted(p.items()) if v]

    return final[ind-2]
1
Rafael Aguilar On

This isn't a Python issue, the problem is in your calculation on how you calculate the results. When you do final[51] it actually returns the value that holds that position, do this:

# Modify your line
# return final[ind-1]
# return final

# Call your method
o_final = nthPrime(100)
for k in range(len(o_final)):
    print(k, y[k])

Then you realize that at pos 93 you reach the next one and keep incrementing.

4
YOBA On

A more efficient way to do this would be a recursive function: I'll put some explanation in the code.

def nthPrime(ind):
    first_prime=1                              #first prime number
    number = 1                                 # all numbers that we will check, this will be incremented
    prime_numbers = [first_prime]              # The list of prime numbers we will find

    def findPrimeInPosition(ind, number):
        if ind > len(prime_numbers):           # This recursive function will exit if find a sufficient number of primes
            number+=1                          # incrementing to check the next number
            is_prime = True                    # Assuming number is a prime

            for p in prime_numbers[1:]:        # Check if it is a prime
                if not number % p:
                    is_prime = False

            if is_prime:
                prime_numbers.append(number)   # Add to the list of primes

            findPrimeInPosition(ind, number) 
        return prime_numbers[-1]               # Get the last element found
    return findPrimeInPosition(ind, number)

Example of usage:

print nthPrime(47)
>> 199
print nthPrime(48)
>> 211