用python写一个程序用筛法求出n(2≤n≤1000)以内的全部质数。 【输入】 输入n。 【输出】 输出若干个数字,用一个空格隔开,表示由小到大的质数。 【输入样例】 10 【输出样例】 2 3 5 7
时间: 2023-06-04 18:06:58 浏览: 217
python使用筛选法计算小于给定数字的所有素数
以下是Python代码实现:
```
def sieve_of_eratosthenes(n):
prime = [True] * (n+1)
prime[0] = prime[1] = False
for i in range(2, int(n**0.5)+1):
if prime[i]:
for j in range(i*i, n+1, i):
prime[j] = False
return [i for i in range(2, n+1) if prime[i]]
n = int(input())
primes = sieve_of_eratosthenes(n)
for prime in primes:
print(prime, end=' ')
```
要求筛法求出n以内的全部质数,我们可以使用埃氏筛法,即从小到大枚举每个数,如果该数为质数,则标记它的倍数都不是质数。最终未被标记的数就是质数。
函数`sieve_of_eratosthenes`实现了埃氏筛法,输入参数`n`表示求n以内的质数,返回值为一个列表,其中保存了所有的质数。
最后我们调用`sieve_of_eratosthenes`函数得到质数列表,并逐个输出质数即可。
阅读全文