python使用筛选法求解小于n的素数
时间: 2024-10-12 22:04:34 浏览: 15
在Python中,我们可以使用筛选法(埃拉托斯特尼筛法,Sieve of Eratosthenes)来找到小于某个给定整数n的所有素数。这是一种古老而高效的算法,步骤大致如下:
1. 创建一个从2到n的布尔列表,初始化所有数字为True,表示它们都可能是素数。
2. 开始从最小的质数2开始,将它的倍数标记为非素数(即将其对应的布尔值设为False)。因为除了它自身,不会有其他的因子。
3. 接着找出下一个未被标记的数(也就是当前最小的质数),重复步骤2,直到遍历完所有小于等于√n的数。
4. 遍历结束后,列表中仍然为True的元素就是素数。
以下是Python代码实现:
```python
def sieve_of_eratosthenes(n):
primes = [True] * (n + 1)
p = 2
while p * p <= n:
if primes[p]:
for i in range(p * p, n + 1, p):
primes[i] = False
p += 1
prime_numbers = [i for i, is_prime in enumerate(primes) if is_prime]
return prime_numbers
# 示例:找到小于50的素数
n = 50
result = sieve_of_eratosthenes(n)
print("小于{}的素数有:{}".format(n, result))
阅读全文