埃拉托斯特尼筛法是一种用于生成质数的算法。在这个算法中,我们首先创建一个长度为n+1的布尔数组,初始化所有元素为True。然后,我们从2开始,将所有的倍数都标记为False,直到n的平方根。最后,我们返回所有布尔数组中值为True的索引,即为质数。
下面是一个使用生成器和递归跳过步骤的示例代码:
def sieve_of_eratosthenes(n):
primes = [True] * (n+1)
primes[0] = primes[1] = False
def mark_multiples(p):
for i in range(p*p, n+1, p):
primes[i] = False
def generate_primes():
for p in range(2, int(n**0.5)+1):
if primes[p]:
yield p
mark_multiples(p)
yield from generate_primes()
for p in range(int(n**0.5)+1, n+1):
if primes[p]:
yield p
n = 100
primes = list(sieve_of_eratosthenes(n))
print(primes)
在这个例子中,我们使用了两个嵌套函数。generate_primes
函数是一个生成器,用于生成质数。它从2开始迭代到n的平方根,如果当前数字是质数,则返回该数字,并调用mark_multiples
函数标记所有倍数为False。mark_multiples
函数使用递归的方式标记所有倍数为False。
最后,我们通过yield from generate_primes()
将生成器的结果逐个返回,并通过循环检查剩余的数字是否为质数。
输出结果为:[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97],即为100以内的所有质数。