判断一个数是否为素数的三种方法(附注释)
判断一个数是否为素数是编程中的一个常见问题。下面是三种不同的方法来判断一个数是否为素数,每种方法都附有详细注释。
方法一:朴素算法
def is_prime_naive(n):
"""判断一个数是否为素数的朴素算法"""
if n <= 1:
return False
for i in range(2, n):
# 如果 n 能够被 i 整除,说明 n 不是素数
if n % i == 0:
return False
return True
# 使用示例
print(is_prime_naive(11)) # 输出: True
print(is_prime_naive(12)) # 输出: False
注释:对于一个整数 n,遍历从 2 到 n-1 的所有整数,检查是否能整除 n。如果能,则 n 不是素数。该方法对大数效率较低。
方法二:改进的算法
def is_prime_improved(n):
"""判断一个数是否为素数的改进算法"""
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
# 检查是否能被 i 或 i+2 整除
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
# 使用示例
print(is_prime_improved(11)) # 输出: True
print(is_prime_improved(12)) # 输出: False
注释:该算法基于这样一个事实:所有大于 3 的素数都可以表示为 6k ± 1 的形式。算法在检查是否被 2 或 3 整除后,迭代检查 6k ± 1 的所有可能性,直到平方根 n。
方法三:埃拉托斯特尼筛法(用于寻找一定范围内的所有素数)
def sieve_of_eratosthenes(limit):
"""埃拉托斯特尼筛法,用于在 2 到 limit 范围内寻找所有素数"""
is_prime = [True] * (limit + 1)
p = 2
while (p * p <= limit):
# 如果当前数是素数
if is_prime[p]:
# 更新所有 p 的倍数为非素数
for i in range(p * p, limit + 1, p):
is_prime[i] = False
p += 1
# 返回所有素数
prime_numbers = [p for p in range(2, limit + 1) if is_prime[p]]
return prime_numbers
# 使用示例
print(sieve_of_eratosthenes(30)) # 输出: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
注释:埃拉托斯特尼筛法用于查找某一范围内的所有素数。首先假定所有数字都是素数,然后反复过滤掉素数的倍数(非素数),最终留下的都是素数。
这三种方法涵盖了从简单到复杂,从单个数到多个数的场景,适用于不同的应用需求。