更好的素数算法

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

我想当程序找到一个素数时，它会在 n 上加 1，然后 while 循环处理直到找到第 50 个素数。但它没有，如果我也使用这个素数是错误的，与我想做的无关。

如何实现这个算法，显然改变range()函数的最后一个元素不起作用。
有better/elegantalgorithm/way吗？如果我想找到 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]

注意小编辑 添加 OP 包含但我最初忽略的 candidate<prime**2 测试。

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

以运行时间计算：

Answer 2

首先，为了与 python 2 向后兼容，我在根 x 的四舍五入处添加了一个 int()。

根据我对你的问题的理解，你正在寻找这样的东西：

cnt = 1
maximum=50 #Specify the number you don't want the primes to exceed
print (2)
n=20 #highest number 
while cnt<maximum: #
    for x in range(3,n,2): #using "n" as you hoped
        div = False
        for y in range(2,int(round(x**0.5)+1)):
            if x%y == 0:
                div = True
        if div == False:
            if x<maximum: #we only want to print those up to the maximum
                print str(x)
            else: #if it is greater than the maximum, break the for loop
                break
            cnt += 1
    break #break the while loop too.
print ("\nThere are {} prime numbers.".format(cnt))

这给了我正确的素数。至于 better/more 优雅的解决方案。如果您想要速度更好，请使用经过优化的库，或者查看 this 以获取快速程序的示例。优雅是主观的，所以我会把它留给互联网的其他部分。

更好的素数算法

Better algorithm on prime numbers

python

algorithm

primes

python-3.4