给定两个正整数,你需要求出这个范围内的所有质数。 说明 输入 输入两个正整数n,m(1 < n < m <= 10^7) 输出 从小到大,依次输出
时间: 2025-02-04 10:28:50 浏览: 37
要找出两个正整数之间的所有质数,我们可以使用埃拉托斯特尼筛法(Sieve of Eratosthenes)来高效地解决这个问题。以下是具体的步骤和代码实现:
1. 初始化一个布尔数组,数组的索引表示数字,值表示该数字是否为质数。初始时假设所有数字都是质数。
2. 从2开始,依次将每个质数的倍数标记为非质数。
3. 最后,遍历数组,输出所有被标记为质数的数字。
以下是Python代码实现:
```python
def sieve_of_eratosthenes(n, m):
# 初始化布尔数组,假设所有数字都是质数
is_prime = [True] * (m + 1)
is_prime[0], is_prime[1] = False, False
# 埃拉托斯特尼筛法
for i in range(2, int(m ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, m + 1, i):
is_prime[j] = False
# 输出范围内的所有质数
for i in range(n, m + 1):
if is_prime[i]:
print(i)
# 输入两个正整数
n, m = map(int, input().split())
# 调用函数
sieve_of_eratosthenes(n, m)
```
这个代码首先初始化一个布尔数组`is_prime`,然后使用埃拉托斯特尼筛法将非质数标记为`False`。最后,遍历数组,输出所有被标记为`True`的数字,即质数。
阅读全文
相关推荐


















