埃拉托斯特尼筛法(Sieve of Eratosthenes)是一种用于求解素数的算法。它的基本思想是从2开始,将每个素数的倍数都标记为合数,直到遍历完所有小于给定数的数。
以下是一个使用Python编写的示例代码:
def sieve_of_eratosthenes(n):
# 创建一个布尔数组,用于标记数是否为素数
is_prime = [True] * (n+1)
is_prime[0] = is_prime[1] = False # 0和1不是素数
# 从2开始遍历,将所有素数的倍数标记为合数
p = 2
while p * p <= n:
if is_prime[p]:
for i in range(p * p, n+1, p):
is_prime[i] = False
p += 1
# 收集所有素数
primes = []
for i in range(2, n+1):
if is_prime[i]:
primes.append(i)
return primes
# 测试代码
n = 30
primes = sieve_of_eratosthenes(n)
print("小于等于%d的素数有:" % n)
print(primes)
运行结果:
小于等于30的素数有:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
以上代码中,我们首先创建一个布尔数组is_prime
,用于标记数是否为素数。初始时,所有数都被认为是素数(布尔值为True
)。
然后,从2开始遍历数组,如果当前数是素数,则将其所有倍数标记为合数(布尔值为False
)。遍历范围为2到$\sqrt{n}$,因为大于$\sqrt{n}$的数的倍数已经被之前的素数标记过了。
最后,我们收集所有标记为素数的数,即为结果。
这样就可以使用埃拉托斯特尼筛法求解素数了。
上一篇:埃拉托斯特尼筛法的运行时