4、使用集合实现筛选法求素数。
时间: 2024-10-23 15:11:07 浏览: 36
Eratosthenes筛选法求质数.rar
在编程中,我们可以使用集合(如列表或数组)结合筛选法(也称为埃拉托斯特尼筛法)来找出一定范围内的素数。以下是基本的步骤:
1. 创建一个布尔型数组,长度从2到目标最大值,初始全部设为True,因为2是最小的质数。
2. 开始遍历数组,从第一个质数2开始,将它的所有倍数标记为非素数。例如,如果当前是2,那么4,6,8...等都是它的倍数,所以在对应的索引位置设置为False。
3. 检查下一个未标记为非素数的数字,它是新的质数。然后继续这个过程,将找到的新质数的所有倍数标记掉。
4. 当遍历完整个数组后,剩下的所有索引为True的元素就是素数。
下面是使用Python实现的一个简单版本:
```python
def sieve_of_eratosthenes(n):
primes = [True] * (n+1)
primes[0], primes[1] = False, False
for i in range(2, int(n**0.5) + 1):
if primes[i]:
for j in range(i*i, n+1, i):
primes[j] = False
return [i for i, is_prime in enumerate(primes) if is_prime]
# 示例
primes_in_range = sieve_of_eratosthenes(30)
print(primes_in_range) # 输出:[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
```
阅读全文