如何优化埃拉托斯特尼筛算法以加快素数生成速度？

埃拉托色尼筛法

埃拉托色尼筛法是一种古老的算法，但今天仍然被用作一种简单而有效的方法来查找低于给定数字的所有素数。该算法的工作原理是迭代地标记每个素数的倍数，从 2 开始。

这是埃拉托斯特尼筛法的 Python 实现：

def sieve_of_eratosthenes(n):
    """Return a list of all prime numbers below n."""

    # Create a list of all numbers from 2 to n.
    numbers = list(range(2, n + 1))

    # Iterate over the numbers in the list.
    for i in range(2, int(n ** 0.5) + 1):

        # If the number is prime, mark off all its multiples.
        if numbers[i] != -1:
            for j in range(i * i, n + 1, i):
                numbers[j] = -1

    # Return the list of prime numbers.
    return [i for i in numbers if i != -1]

这个算法实现起来相对简单，而且效率很高。例如，它可以在现代计算机上大约 0.1 秒内找到 100 万以下的所有素数。

时间复杂度

埃拉托斯特尼筛法的时间复杂度为 O(n log log n) 。这意味着该算法需要 O(n) 时间来创建从 2 到 n 的所有数字的列表，并且需要 O(log log n) 时间来标记每个素数的所有倍数。

可以做得更快吗？

有几种方法可以使埃拉托斯特尼筛变得均匀更快：

• 使用更高效的数据结构。从2到n的所有数字的列表可以存储在更高效的数据结构中，例如位向量。这可以减少算法的空间需求并提高其性能。
• 使用更高效的标记算法。可以使标记每个素数的所有倍数的算法更加高效通过使用筛轮。这可以将算法的时间复杂度降低到 O(n)。
• 并行化算法。可以并行化算法以利用现代计算机上的多个内核。这可以进一步提高算法的性能。

这是埃拉托斯特尼筛法的更快版本的 Python 实现：

import numpy as np

def sieve_of_eratosthenes_fast(n):
    """Return a list of all prime numbers below n."""

    # Create a bit vector to store the prime numbers.
    primes = np.ones(n // 2 + 1, dtype=np.bool)

    # Mark off all the multiples of 2.
    primes[3::2] = False

    # Iterate over the odd numbers from 3 to n.
    for i in range(3, int(n ** 0.5) + 1, 2):

        # If the number is prime, mark off all its multiples.
        if primes[i // 2]:
            primes[i * i // 2::i] = False

    # Return the list of prime numbers.
    return [2] + [2 * i + 1 for i in range(1, n // 2 + 1) if primes[i]]

该算法比原始版本更快埃拉托斯特尼筛法，它可以在现代计算机上大约 0.01 秒内找到 100 万以下的所有素数电脑。

以上是如何优化埃拉托斯特尼筛算法以加快素数生成速度？的详细内容。更多信息请关注PHP中文网其他相关文章！