埃拉托斯特尼筛法(Sieve of Eratosthenes)是一种用于找出一定范围内所有素数的算法。该算法使用一个布尔数组来标记每个数字是否为素数,从2开始,将所有的倍数标记为非素数,直到数组中的所有数字都被遍历完。
以下是一个使用埃拉托斯特尼筛法的代码示例来找出超过200,000的素数:
def sieve_of_eratosthenes(n):
# 创建一个布尔数组来标记每个数字是否为素数
is_prime = [True] * (n+1)
# 0和1不是素数,将其标记为非素数
is_prime[0] = is_prime[1] = False
# 使用埃拉托斯特尼筛法,将所有的倍数标记为非素数
for i in range(2, int(n**0.5)+1):
if is_prime[i]:
for j in range(i*i, n+1, i):
is_prime[j] = False
# 返回所有的素数
primes = []
for i in range(2, n+1):
if is_prime[i]:
primes.append(i)
return primes
n = 200000
primes = sieve_of_eratosthenes(n)
print(primes)
在上述代码中,我们首先创建一个布尔数组 is_prime
来标记每个数字是否为素数,初始时将所有数字都标记为素数。然后,我们从2开始遍历数组,如果当前数字为素数,则将其所有的倍数标记为非素数。最后,我们遍历数组,将所有标记为素数的数字添加到 primes
数组中,并打印出结果。
但需要注意的是,上述代码中使用的是普通的埃拉托斯特尼筛法,当超过200,000之后,该算法可能会变得较慢。如果要找出更大范围内的素数,可以考虑使用更高效的算法,如改进的埃拉托斯特尼筛法(如线性筛法)或米勒-拉宾素性测试等。
上一篇:埃拉托斯特尼筛法求素数