提示信息

判断一个数是否为素数的三种方法(附注释)

流光 已关注

判断一个数是否为素数是编程中的一个常见问题。下面是三种不同的方法来判断一个数是否为素数,每种方法都附有详细注释。

方法一:朴素算法

  1. def is_prime_naive(n):
  2. """判断一个数是否为素数的朴素算法"""
  3. if n <= 1:
  4. return False
  5. for i in range(2, n):
  6. # 如果 n 能够被 i 整除,说明 n 不是素数
  7. if n % i == 0:
  8. return False
  9. return True
  10. # 使用示例
  11. print(is_prime_naive(11)) # 输出: True
  12. print(is_prime_naive(12)) # 输出: False

注释:对于一个整数 n,遍历从 2 到 n-1 的所有整数,检查是否能整除 n。如果能,则 n 不是素数。该方法对大数效率较低。

方法二:改进的算法

  1. def is_prime_improved(n):
  2. """判断一个数是否为素数的改进算法"""
  3. if n <= 1:
  4. return False
  5. if n <= 3:
  6. return True
  7. if n % 2 == 0 or n % 3 == 0:
  8. return False
  9. i = 5
  10. while i * i <= n:
  11. # 检查是否能被 i 或 i+2 整除
  12. if n % i == 0 or n % (i + 2) == 0:
  13. return False
  14. i += 6
  15. return True
  16. # 使用示例
  17. print(is_prime_improved(11)) # 输出: True
  18. print(is_prime_improved(12)) # 输出: False

注释:该算法基于这样一个事实:所有大于 3 的素数都可以表示为 6k ± 1 的形式。算法在检查是否被 2 或 3 整除后,迭代检查 6k ± 1 的所有可能性,直到平方根 n。

方法三:埃拉托斯特尼筛法(用于寻找一定范围内的所有素数)

  1. def sieve_of_eratosthenes(limit):
  2. """埃拉托斯特尼筛法,用于在 2 到 limit 范围内寻找所有素数"""
  3. is_prime = [True] * (limit + 1)
  4. p = 2
  5. while (p * p <= limit):
  6. # 如果当前数是素数
  7. if is_prime[p]:
  8. # 更新所有 p 的倍数为非素数
  9. for i in range(p * p, limit + 1, p):
  10. is_prime[i] = False
  11. p += 1
  12. # 返回所有素数
  13. prime_numbers = [p for p in range(2, limit + 1) if is_prime[p]]
  14. return prime_numbers
  15. # 使用示例
  16. print(sieve_of_eratosthenes(30)) # 输出: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

注释:埃拉托斯特尼筛法用于查找某一范围内的所有素数。首先假定所有数字都是素数,然后反复过滤掉素数的倍数(非素数),最终留下的都是素数。

这三种方法涵盖了从简单到复杂,从单个数到多个数的场景,适用于不同的应用需求。

    遇到难题? "AI大模型GPT4.0、GPT" 是你的私人解答专家! 点击按钮去提问......
流光 关注 已关注

最近一次登录:2024-11-20 18:52:58   

暂时还没有签名,请关注我或评论我的文章
×
免费图表工具,画流程图、架构图