使用筛选法求出300以内的素数并输出
时间: 2024-11-13 16:41:56 浏览: 9
筛选法,也称为埃拉托斯特尼筛法(Sieve of Eratosthenes),是一种古老而高效的寻找一定范围内质数的经典算法。以下是使用这个方法找出300以内所有素数的步骤:
1. 创建一个布尔数组,大小为301,初始全部标记为`true`。因为0和1不是质数,所以索引0和1对应的值设为`false`。
2. 从2开始遍历数组,因为2是最小的质数。如果当前数i是`true`(即它是质数),那么将它所有的倍数(除了自身)都标记为`false`。例如,对于2,我们将4、6、8...等都标记为非质数。
3. 每次检查完一个质数i,就继续找到下一个未被标记为非质数的数,即下一位的`true`值,作为下一个待处理的质数。
4. 当遍历到数组末尾时,那些仍然标记为`true`的数就是300以内的所有质数。
以下是这个过程的一个简化的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 in range(n+1) if primes[i]]
# 输出300以内的素数
prime_list = sieve_of_eratosthenes(300)
print(prime_list)
阅读全文