使用筛选法求出 300以内的素数并输出,结果如下图所示。不得使用自定义函数实现筛选法 python
时间: 2024-12-11 22:37:36 浏览: 13
基于Jupyter 使用列表实现筛选法求素数(python)
筛选法,也称为埃拉托斯特尼筛法(Sieve of Eratosthenes),是一种古老的算法,用于找出一定范围内的所有质数。以下是使用Python实现筛选法找出300以内素数的步骤:
```python
def sieve_of_eratosthenes(n):
primes = [True] * (n + 1) # 创建一个布尔数组表示所有数是否为素数,默认为True
primes[0], primes[1] = False, False # 0和1不是素数
for i in range(2, int(n**0.5) + 1): # 只需检查到sqrt(n),因为大于该值的因子必定小于它
if primes[i]: # 如果i是素数
for j in range(i*i, n+1, i): # 将i的倍数标记为合数
primes[j] = False
# 输出所有的素数
for i, is_prime in enumerate(primes):
if is_prime and i > 1: # 排除1这个特殊情况
print(i)
sieve_of_eratosthenes(300)
```
这段代码首先初始化一个布尔数组,然后从2开始,将它的倍数标记为非素数。循环到平方根范围内,最后只保留那些被标记为素数的数字。
运行这段代码,你会得到300以内的所有素数列表。
阅读全文