查找给定整数 N 以下的所有素数的最快方法是什么？

列出 N 以下所有素数的最快方法

此代码片段提供了有效生成素数列表的方法的 Python 实现最多给定整数。

    def get_primes(n):
        numbers = set(range(2, n + 1))
        primes = []
        while numbers:
            p = numbers.pop()
            primes.append(p)
            numbers.difference_update(set(range(p * p, n + 1, p)))
        return primes

时间复杂度：

给定代码的时间复杂度为 O(n log log n)，因为它使用埃拉托斯特尼筛法来计算素数。

实现说明:

• 代码初始化一组数字，其中包含从 2 到n.
• 它通过将尚未标记的最小数字的所有倍数标记为合数，迭代地从数字中删除非素数。在更新数字时，通过采用当前素数的步幅来跳过这些倍数。
• 当数字为空时，代码停止，找到的素数列表以素数形式返回。

潜在问题：

实现中存在一个潜在问题，它将起始数字标记为素数当它只应考虑从 2 到 n 的数字时。这可以通过从 2 而不是 0 开始循环来解决。

用法：

要使用此实现，您可以调用 get_primes 函数并传递所需的上限绑定为参数。例如，要查找 1000 以内的所有素数，您可以使用：

primes = get_primes(1000)

输出：

代码的输出将是素数列表最大到指定整数的数字。例如，运行 n = 1000 的代码将产生以下输出：

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ..., 977]

以上是查找给定整数 N 以下的所有素数的最快方法是什么？的详细内容。更多信息请关注PHP中文网其他相关文章！