python - 超出内存限制以找到第 N 个素数

Question

我正在解决一个问题（在网站上）打印第 N 个素数，其中 N 是用户输入。该问题修复了这些限制 1s，512 MB。我在下面写了那个代码。

n = int(input())
r = (n+1)**2
nth = n - 1
d = [x for x in range(2, r)]
non_prime = []
for i in range(2, r):
    for x in d:
        if i % x == 0 and x != 1 and x != i:
            non_prime.append(i)


non_prime = list(set(non_prime))
prime_numbers = [x for x in d if x not in non_prime]
print(prime_numbers[nth])

现在代码运行良好，但提交后显示超出内存限制。如何在不过度更改我的代码的情况下解决这个问题？

（我知道有更简单的方法可以解决这个问题。但我自己解决了。）

Answer 1

您使用的方法会检查每个数字，直到给定数字的平方。我发现将素数添加到列表并检查其长度要容易得多。使用这种方法，它检查的数字很少，并且可以快速运行。

def getPrime(num):
    arr = []
    x = 2
    while len(arr) < num:
        prime = True
        for divisor in range(2, x):
            if x % divisor == 0 and prime == True:
                prime = False
        if prime == True:
            arr.append(x)
        x += 1
    return arr[num - 1]

我鼓励您改进此代码，因为它是初级的。

编辑：我更正了一个变量名。