用埃拉托色尼筛选法输出 100 以内的所有素数。
时间: 2023-09-11 16:07:26 浏览: 184
筛选法求质数表-ACM竞赛常用算法与数据结构
好的,我可以帮您解答这个问题。以下是埃拉托色尼筛选法输出 100 以内的所有素数的代码:
```python
# 初始化列表,用布尔值表示每个数是否为素数
is_prime = [True] * 101
is_prime[0] = is_prime[1] = False
# 遍历 2 到 100,将素数的倍数标记为合数
for i in range(2, int(100 ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, 101, i):
is_prime[j] = False
# 输出素数
for i in range(2, 101):
if is_prime[i]:
print(i, end=' ')
```
这个算法首先将所有数都初始化为素数,然后从 2 开始遍历到 100 的平方根(因为超过平方根的因子肯定已经被标记过了),如果当前数是素数,就将它的倍数都标记为合数。最后输出所有素数即可。
阅读全文