埃拉托斯特尼筛法(Sieve of Eratosthenes)是一种用于找出一定范围内所有素数的算法。其主要思想是从2开始,不断将素数的倍数标记为合数,直到遍历完所有数。
以下是一个使用Python语言实现埃拉托斯特尼筛法的代码示例:
def sieve_of_eratosthenes(n):
# 创建一个长度为n+1的布尔类型列表,用于标记数字是否为素数
is_prime = [True] * (n+1)
is_prime[0] = is_prime[1] = False
# 从2开始遍历到n的平方根
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
# 将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
# 示例:找出100以内的所有素数
primes = sieve_of_eratosthenes(100)
print(primes)
代码解释:
is_prime
,用于标记数字是否为素数。初始化为全部为True,两个最小的素数0和1被标记为False。is_prime[i]
为True),则将其倍数的数字都标记为合数(即is_prime[j] = False
)。primes
中。primes
,即为找出的所有素数。以上代码示例使用埃拉托斯特尼筛法找出了100以内的所有素数,并将结果打印输出。你可以根据需要修改参数n
来寻找其他范围内的素数。