python编写程序,使用筛选法求解小于n的所有素数。
时间: 2024-11-29 15:38:52 AIGC 浏览: 104
在Python中,我们可以使用筛选法(也称为埃拉托斯特尼筛法)来找出小于给定整数n的所有质数。以下是使用这个算法的一个简单实现:
```python
def sieve_of_eratosthenes(n):
primes = [True] * (n + 1) # 初始化一个布尔数组,所有元素都默认为质数
p = 2
while p * p <= n:
if primes[p]: # 如果p是质数
for i in range(p * p, n + 1, p): # 将p的倍数标记为非质数
primes[i] = False
p += 1
# 返回所有的质数
prime_numbers = [p for p in range(2, n+1) if primes[p]]
return prime_numbers
# 示例
n = int(input("请输入一个正整数: "))
print(sieve_of_eratosthenes(n))
```
在这个代码中,我们首先创建一个布尔数组`primes`,然后从最小的质数2开始,将它的倍数标记为非质数。遍历到`sqrt(n)`就足够了,因为大于`sqrt(n)`的合数一定有一个因子在之前已经被标记了。最后,筛选出剩下的质数并返回。
阅读全文
相关推荐










