python查找前n个质数的算法
时间: 2025-02-11 11:38:13 浏览: 36
在Python中查找前n个质数,可以使用一种常见的筛选法,称为埃拉托斯特尼筛法(Sieve of Eratosthenes)。这是一种简单而有效的寻找连续范围内质数的算法。以下是实现该算法的基本步骤:
1. 创建一个列表,初始全为True,表示从0到最大范围内的所有数字都是潜在的质数。
2. 首先设置第一个质数为2,然后遍历这个列表,将2的所有倍数标记为False(因为除了它自身,它的倍数不可能是质数)。
3. 找到下一个未被标记为False的数字,即为当前的质数,并记录下来。
4. 继续重复第2、3步,直到找到n个质数。
下面是一个简单的Python函数实现:
```python
def find_n_primes(n):
limit = int(n * sqrt(2)) + 1 # 确定搜索的最大范围,理论最多只需要到√n * n
primes = [True] * limit # 初始全部设为True
primes[0], primes[1] = False, False # 0和1不是质数
for i in range(2, int(sqrt(limit)) + 1): # 只需检查到√limit即可
if primes[i]: # 如果i是质数
for j in range(i*i, limit, i): # 将i的倍数标记为非质数
primes[j] = False
result = []
for i, is_prime in enumerate(primes): # 遍历列表,收集前n个质数
if is_prime and i > n - 1: # 当找到n个质数就停止
break
else:
result.append(i + 1) # 因为是从0开始计数的,所以加上1
return result
# 示例:获取前10个质数
n = 10
prime_numbers = find_n_primes(n)
print(f"前{n}个质数是:{prime_numbers}")
阅读全文
相关推荐


















