素数检查器，包括非素数

Question

我正在尝试求解Project Euler编号7。

通过列出前六个素数：2、3、5、7、11和13，我们可以看到第六个素数是13。
第1001个素数是什么？

我想到的第一件事是使用列表的长度。这是一个非常无效的解决方案，因为它花了一分钟多的时间。这是使用过的代码。

def ch7():
primes = []
x = 2
while len(primes) != 10001:
for i in range(2, x):
if x % i == 0:
break
else:
primes.append(x)
x += 1

print(primes[-1])
ch7()
# Output is: 104743. 

这很有效，但我想找到更快的解决方案。因此，我做了一点研究，发现为了知道一个数字是否是素数，我们需要测试它是否可以被任何数字整除，直到它的平方根。例如，为了知道100是否为素数，我们不需要把它除以100以内的每个数，而只需要除以10。

当我实现这个发现时，奇怪的事情发生了。该算法包含一些非素数。确切地说是66个。这是调整后的代码：

import math
primes = []
def ch7():
x = 2
while len(primes) != 10001:
for i in range(2, math.ceil(math.sqrt(x))):
if x % i == 0:
break
else:
primes.append(x)
x += 1

print(primes[-1])
ch7()
# Output is 104009

这个解需要不到一秒钟的时间，但它包含了一些非素数。我使用math.ceil((来获得int而不是float，但我认为这应该不是问题，因为它仍然通过x的平方根来测试每个int。

谢谢你的建议

Answer 1

您的解决方案生成素数的list，但除了提取最后一个元素外，不使用该list。我们可以抛出list，并通过将2视为特例，只测试奇数，将中的代码时间缩短一半：

def ch7(limit=10001):  # assume limit is >= 1
prime = 2
number = 3
count = 1
while count < limit:
for divisor in range(3, int(number ** 0.5) + 1, 2):
if number % divisor == 0:
break
else:  # no break
prime = number
count += 1
number += 2
return prime
print(ch7())

但是，如果你要收集一个素数的list，你可以使用这个list，通过使用这些素数作为除数而不是奇数来提高程序的速度(对于使用中的测试极限，大约为10%(：

def ch7(limit=10001):  # assume limit is >= 1
primes = [2]
number = 3
while len(primes) < limit:
for prime in primes:
if prime * prime > number:  # look no further
primes.append(number)
break
if number % prime == 0:  # composite
break
else:  # may never be needed but prime gaps can be arbitrarily large
primes.append(number)
number += 2
return primes[-1]

print(ch7())

顺便说一句，你的第二个解决方案，即使有你在评论中提到的+ 1修复，也会在正确答案之外出现一个素数。这是由于您的代码(错误(处理素数2的方式造成的。