Python while 循环不会退出（初学者）

Question

最后的 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])

Answer 1

它不会退出的原因是因为您对潜在素数的搜索 space 太大了。你的桌面没那么快！他们有超级计算机试图计算这些东西。

for i in xrange(primes[-1], sys.maxint):

首先，尝试将其更改为更合理的内容：

for i in xrange(primes[-1], 10000):

您会看到您的循环确实退出了。

编辑：

您可以对这个问题进行一些不错的优化。首先，您应该递增 2 以跳过所有偶数：

for i in xrange(primes[-1], sys.maxint, 2):

其次，您只需要测试最大为潜在素数的 平方根 的除数。

for i in xrange(2,n**(0.5)):

原因是任何两个乘积为 n 的数字，其中一个总是小于 n 的平方根 - 因此如果您还没有找到除数当您达到 n 的平方根时，您可以停止。这大大减少了搜索 space 更大的数字。

Answer 2

正如所解释的那样，您的循环需要计算直到 sys.maxint 的所有素数，这需要非常非常长的时间（尤其是在 64 位平台上！） .

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

这里的关键是尽快跳出inner循环，这样就可以回到outer循环.内部循环正在检查您是否有一个 足够大 素数，这与您的问题无关；外循环正在检查您是否有足够个素数。所以您想在找到每个素数后检查外循环。

一种方法是更改内部循环，使其在一个质数后 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 是否是素数。但这样做是一个更大的答案。 :)

Python while 循环不会退出（初学者）

Python while loop won't exit (Beginner)

python

while-loop