满足要求时退出定义的函数

Question

我正在尝试尽快生成素数，检查多个版本的代码并比较每个版本的速度。我已经转向使用 Sundaram 筛子的版本。网上关于这个的解释很多，我就不一一解释了。基本上，它会标记出不可能是素数的数字，然后将剩余的数字乘以 2 加一，然后这些数字都将成为素数。用代码实现相当简单。该函数采用某个数字 n，并查找所有小于或等于 n 的素数。然而，我需要它来找到前 n 个素数，而不是这样做。有一个定理说第 n 个素数总是小于 2^n。然而，使用这个函数来查找大量素数是极其不现实的，因为我必须搜索最多 2^n 个素数。我正在尝试找到一种方法来检查

len(prime_list) == n

，然后从函数中中断，然后只是

return overall_time, prime_list

（prime_list 对于我想做的事情并不是真正需要的，但它不会影响程序） 。这是我目前定义该函数的方式：

def SieveOfSundaram(n):
    prime_list = [2]
    nNew = int((n - 1) / 2)
    marked = [0] * nNew
    start_time = time.perf_counter_ns()
    for i in range(1, (nNew + 1)):
        j = i
        while (i + j + (2 * i * j)) <= nNew:
            marked[i + j + (2 * i * j)] = 1
            j += 1

    for i in range(1, nNew + 1):
        if marked[i] == 0:
            prime_list.append((2 * i + 1))
    end_time = time.perf_counter_ns()
    overall_time = end_time - start_time

    return prime_list, overall_time

我尝试重写代码，而不是在长度 nNew 的开头定义一个列表，而是在第一个 for 循环的每次迭代中向列表中添加一个新元素。然而，我无法让它工作，因为你需要在确定素数之前标记出所有元素，所以你不能只检查它是否是素数而不每次都进行所有计算，并且因为意图是为了让它很快（我目前最好的时间是 5000 个素数的 0.0616 秒），这样做会破坏整个目的。谢谢。

Answer 1

一个标准的解决方案是只做合理大小的块，不会超出太多。例如，大小为

10*sqrt(n)

的块将允许您进行

O(sqrt(n) log(n))

检查并通过

O(sqrt(n))

工作进行超调。这比

O(n)

检查好多了。

但是对于这一点，您可能想得太多了。对于前 5000 个素数，以下几乎未优化的方法大约需要 0.01 秒。

def primes ():
    yield 2
    yield 3
    f = {}
    n = 5
    for p in primes():
        if p == 2:
            continue
        p2 = p*p
        while n < p2:
            if n in f:
                double_p = f.pop(n)
                m = n + double_p
                while m in f:
                    m += double_p
                f[m] = double_p
            else:
                yield n
            n += 2
        f[n] = 2*p

def n_primes (n):
    p_list = []
    for p in primes():
        p_list.append(p)
        if n <= len(p_list):
            return p_list

import time
count = 0
s = 0
start_time = time.perf_counter_ns()
prime_list = n_primes(5000)
end_time = time.perf_counter_ns()
print(s, (end_time - start_time) / 10**9)