筛子似乎是正确的方法，与向OP告知的算法不同。如果我们筛查最多n且n是质数，我们就完成了。如果没有，我们只需要找到n之后的第一个素数，然后我们知道答案。由于2始终是最坏情况的答案，因此我们无需筛除2 * n。并且，当我们发现增加的质数小于n时，我们可以减小筛子的尺寸，从而减少需要做的打击次数。这是我针对此问题未优化的示例解决方案：

def closest_prime(n):
    if n <= 1:  # handle 0 & 1 as special cases
        return 2

    sieve_limit = 2 * n

    sieve = [False,False] + [True] * (sieve_limit - 2)

    prime_candidate = number = 2

    while number < sieve_limit:
        if sieve[number]:
            if number == n:
                return n  # n is prime

            if number > n:
                if (number - n) < (n - prime_candidate):
                    return number

                return prime_candidate

            prime_candidate = number

            sieve_limit = 2 * n - prime_candidate  # reduce sieve size

            for index in range(number * number,sieve_limit,number):
                sieve[index] = False

        number += 1

    return prime_candidate  # ran off end of sieve

if __name__ == "__main__":
    print(20831428,closest_prime(20831428))
    print(20831429,closest_prime(20831429))

输出

> python3 test.py
20831428 20831323
20831429 20831533
> 

我选择上述测试用例是因为质数20831323和20831533之间存在209的健康差异。注释中引用的代码无法正确处理第二个测试，因为它使用了硬编码的筛子上限。如前所述，该代码未经过优化，例如：

• 我们可以更聪明地处理偶数以减少测试和打击。

• 我们可以将筛分极限调整一个左右，因为在平局的情况下我们将采用较低的素数。

• 如果n - 1是素数，我们可以简单地返回如果n不是素数，甚至不用寻找n之上的第一个素数。

p>