上一篇
质数（素数）是指在大于1的自然数中，除了1和它本身以外不再有其他因数的数。本教程将教你使用Python输出指定范围内的所有质数。
什么是质数？
质数（Prime Number）又称素数，是大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数。例如，2、3、5、7、11等都是质数。
2
3
5
7
11
13
17
19
23
29
方法一：基础循环方法
这是最简单直接的方法，通过循环检查每个数字是否为质数。
实现步骤
- 遍历指定范围内的每个数字
- 对于每个数字，检查它是否能被2到该数平方根之间的任何整数整除
- 如果不能被整除，则该数是质数
- 将质数添加到结果列表中
# 输出指定范围内的质数 - 基础方法
def find_primes(start, end):
primes = []
for num in range(max(2, start), end + 1):
is_prime = True
# 检查2到平方根的范围
for i in range(2, int(num**0.5) + 1):
if num % i == 0:
is_prime = False
break
if is_prime:
primes.append(num)
return primes
# 示例：找出1到50之间的质数
primes = find_primes(1, 50)
print("1-50之间的质数:", primes)
1-50之间的质数: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
方法二：埃拉托斯特尼筛法（高效算法）
这是找出质数的高效算法，特别适合找出较大范围内的所有质数。
算法原理
埃拉托斯特尼筛法的工作原理：
- 创建一个从2到上限的连续整数列表
- 最初令p等于2（第一个质数）
- 从p²开始，标记p的所有倍数（p², p²+p, p²+2p, ...）
- 找到列表中大于p的最小未标记数，令p等于这个数
- 重复步骤3-4直到p²大于上限
- 所有剩余未标记的数就是质数
# 埃拉托斯特尼筛法实现
def sieve_of_eratosthenes(end):
# 创建布尔数组，初始值设为True
is_prime = [True] * (end + 1)
is_prime[0] = False
is_prime[1] = False
# 从2开始到平方根
for num in range(2, int(end**0.5) + 1):
if is_prime[num]:
# 标记所有倍数为False
for multiple in range(num*num, end+1, num):
is_prime[multiple] = False
# 收集所有质数
primes = [num for num in range(2, end+1) if is_prime[num]]
return primes
# 示例：找出100以内的所有质数
primes = sieve_of_eratosthenes(100)
print("100以内的质数:", primes)
100以内的质数: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
方法三：优化版循环（跳过偶数）
在基础方法上优化，跳过偶数（除2外）以提高效率。
优化点
- 2是唯一的偶质数，单独处理
- 只检查奇数
- 检查范围缩小到平方根
# 优化版质数查找（跳过偶数）
def optimized_primes(start, end):
if end < 2:
return []
primes = []
if start <= 2:
primes.append(2)
# 确保从奇数开始
start = max(3, start)
if start % 2 == 0:
start += 1
# 只检查奇数
for num in range(start, end + 1, 2):
is_prime = True
# 检查2到平方根的范围
for i in range(3, int(num**0.5) + 1, 2):
if num % i == 0:
is_prime = False
break
if is_prime:
primes.append(num)
return primes
# 示例：找出50到100之间的质数
primes = optimized_primes(50, 100)
print("50-100之间的质数:", primes)
50-100之间的质数: [53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
算法性能比较
基础循环方法
优点：
- 简单直观，易于理解
- 实现简单
- 适合小范围查找
缺点：
- 时间复杂度高：O(n√n)
- 大范围查找效率低
埃拉托斯特尼筛法
优点：
- 时间复杂度低：O(n log log n)
- 适合大范围查找
- 一次生成所有质数
缺点：
- 需要较多内存
- 实现相对复杂
实际应用场景
质数在编程和计算机科学中有广泛的应用：
- 密码学：RSA加密算法基于大质数的乘积
- 散列函数：使用质数减少冲突
- 随机数生成：质数用于生成更均匀的分布
- 算法优化：在需要避免周期性行为时使用
发表评论