包括非素数在内的素数检查器

Question

我正在尝试解决 Project Euler 7。

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?

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

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，但我认为这应该不是问题，因为它仍然测试每个 int 直到 x 的平方根。

谢谢你的任何建议。

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 的方式所致。

包括非素数在内的素数检查器

Prime checker including non primes

python

primes

python-3.x