埃拉托色尼篩法是一種古老的演算法，但今天仍然被用作一種簡單而有效的方法來找出低於給定數字的所有質數。這個演算法的工作原理是迭代地標記每個質數的倍數，從 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) 時間來標記每個質數的所有倍數。
有幾種方法可以讓埃拉托斯特尼篩變得均勻更快：
這是埃拉托斯特尼篩法的更快版本的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中文網其他相關文章！
