Python while循环不会退出(初学者) - python

最后的while循环不会退出，我也不知道为什么。

import sys

def is_prime(n):
    if n == 3:
        return True
    elif n == 4:
        return False
    else:
        for i in xrange(2,n):
            if n % i == 0:
                return False
        return True

primes = [2, 3]

counter = int(raw_input("Which prime number would you like to find? "))

while len(primes) < counter:
    for i in xrange(primes[-1], sys.maxint):
        if is_prime(i):
            primes.append(i)

print(primes[-1])

python大神给出的解决方案

正如Martin Konecny's answer解释的那样，您的循环需要计算直至sys.maxint的所有素数，这需要非常，非常长的时间(尤其是在64位平台上!)。

但实际上，您不需要sys.maxint的素数，甚至不需要10000的素数。使用他的解决方案，即使您只需要前7个素数，您也将要计算前1229个素数。花费的时间比必要的时间长。更糟糕的是，即使您需要第1400个素数，也只会计算前1229个素数，这意味着您将陷入无限循环，直到10000以下的素数永远存在，即使在10000以下也没有更多素数。

这里的关键是尽快摆脱内循环，以便您可以回到外循环。内部循环正在检查您是否有足够大的素数，这与您的问题无关；外循环正在检查您是否有足够的素数。因此，您想在找到每个素数之后检查外循环。

一种方法是更改​​内部循环，使其在一个素数后仅break消失，从而使您有机会再次检查len:

while len(primes) < counter:
    for i in xrange(primes[-1], sys.maxint):
        if is_prime(i):
            primes.append(i)
            break

实际上，如果执行此操作，甚至可以用无限范围替换该限制，它仍然会完成。

还有一件事:内循环中有一个错误:xrange(primes[-1], sys.maxint)包括primes[-1]。而primes[-1]显然是素数。因此，您将不断重复添加相同的值。您在那里需要一个+ 1。

所以:

while len(primes) < counter:
    for i in itertools.count(primes[-1]+1)
        if is_prime(i):
            primes.append(i)
            break

解决此问题的更好方法是使用实​​际的主筛而不是除数测试。筛子有效地保持了到目前为止找到的每个质数的下一个倍数的超前映射，因此，如果您已经检查了所有值，直到N-1，您就可以非常快速地确定N是否为质数。但这是一个更大的答案。 🙂