python - 更好的素数算法

Question

我正在开发一个将找到第 n 个的程序。素数。例如，通过列出前六个素数:2, 3, 5, 7, 11 和 13，我们可以看到第 6 个素数是 13。我正在尝试制作一个算法，例如，如果我想查看第 50 个素数，我将在 range() 函数的末尾添加 1。我现在正在使用这个算法来寻找素数；

cnt = 1
print (2)
for x in range(3,40,2):
    div = False
    for y in range(2,round(x**0.5)+1):
        if x%y == 0:
            div = True
    if div == False:
        print (x)
        cnt += 1

print ("\nThere is {} prime numbers.".format(cnt))

你看，我输入了 40。但我想把 n 放在那里，例如，直到达到第 50 个素数，将 +1 添加到 n。但它不会喜欢那样，如果我尝试类似的东西；

cnt = 1
n = 40 #example
while cnt<50:
    for x in range(3,n,2):
        #codes
    if div == False:
        n += 1

我认为当程序找到素数时，它会将 +1 添加到 n 并且 while 循环将处理直到找到第 50 个素数。但它没有，如果我也使用这个素数是错误的，与我想做的无关。

• 如何实现这个算法，显然改变 range() 函数的最后一个元素不起作用。

• 是否有更好/优雅的算法/方式？如果我想找到 200.000th 素数，我需要更快的代码。

编辑:我首先使用列表，但是在使用大数字时，我一直遇到 MemoryError。所以我传递它并使用一个变量来计算有多少素数 cnt。

Answer 1

这是一个更快的版本

primes = []
primecount = 0

candidate = 2
while primecount<50:
    is_prime = True
    for prime in primes:
        if candidate%prime == 0:
            is_prime = False
            break
        elif candidate < prime**2:
            break
    if is_prime:
        primes.append(candidate)
        primecount += 1

    candidate += 1
print primes[-1]

注意小修改 添加 candidate<prime**2测试 OP 包含但我最初忽略了。

由于多种原因，您的代码将变得非常慢。如果 2 整除一个数，您知道它不是质数，但您仍在检查是 3 还是 4 或 5... 整除它。因此，您可以在知道它不是素数时立即爆发。另一个主要问题是，如果 2 不整除一个数，则没有理由检查 4 是否也整除它。因此，您可以将注意力集中在检查除法之前是否有质数。

在运行时间方面: