题目描述 给定一个正整数nn,输出[1,n][1,n]范围内的所有素数。 输入描述 一个正整数nn(2≤n≤1062≤n≤106)。 输出描述 每行一个素数,从小到大输出[1,n][1,n]范围内的所有素数。
时间: 2024-03-20 13:41:38 浏览: 109
好的,这是一个关于素数的问题。我可以给你提供一个简单的算法来解决这个问题,它叫做埃拉托色尼筛法(Sieve of Eratosthenes)。
算法步骤如下:
1. 创建一个数组 isPrime,长度为 n+1,用于标记每个数是否为素数,初始值都为 true。
2. 从 2 开始遍历到 $\sqrt{n}$ ,如果当前数 i 为素数,则将数组中 i 的倍数标记为 false。
3. 遍历 isPrime 数组,输出值为 true 的下标,即为素数。
下面是这个算法的 Python 代码实现:
```
import math
def find_primes(n):
isPrime = [True] * (n+1)
isPrime[0], isPrime[1] = False, False
for i in range(2, int(math.sqrt(n))+1):
if isPrime[i]:
j = i * i
while j <= n:
isPrime[j] = False
j += i
primes = []
for i in range(2, n+1):
if isPrime[i]:
primes.append(i)
return primes
```
你可以调用这个函数,并传入你想要求解的正整数 n,函数将会返回所有小于等于 n 的素数。
阅读全文
相关推荐








