Python 3：超过100个指数的列表在指数47之后循环回来。为什么？我该如何阻止呢？

Question

所以这是一个获取第n个质数的函数。我知道它以前已经完成，而且我的方法可能不是很有效（顺便说一句，新编码员过去曾有过少量涉猎）。无论如何，下面的代码有效并且 returns 提供索引的素数。即：

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

但决赛[51-1] returns决赛[3-1]是什么。似乎在索引 47 之后循环并重新开始。我打印了 final 中包含的整个列表。它会打印每个素数，甚至是 47 岁以后的素数。我不确定发生了什么。 python 中的列表是否有一些限制？

代码如下：

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]

Answer 1

这不是Python问题，问题出在您计算结果的方式上。当你做 final[51] 它实际上 returns 保持那个位置的值，这样做：

# 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])

然后你意识到在 pos 93 你到达下一个并继续递增。

Answer 2

你需要计算你的列表中有多少个素数，但你在循环中累积了 final，所以你在循环中多次将所有数字加到极限。 199 后再次从 2 开始。

此外，使用字典和依赖顺序是危险的。你应该在迭代时对它们进行排序。

我的解决方案只计算素数以知道何时结束循环，并在最后组成列表，省略 1 并将索引移动 1。

我还在遍历字典时对字典进行排序以确保：

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]

Answer 3

一种更有效的方法是使用递归函数：我会在代码中做一些解释。

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)

用法示例：

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

Python 3：超过100个指数的列表在指数47之后循环回来。为什么？我该如何阻止呢？

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

python

indexing

loops

iterable

list