质数判定算法的实现

质数（Prime Number）是指大于1且只能被1和自身整除的数。在计算机科学中，判定一个数是否为质数是一个常见的算法问题。

下面将介绍两种常见的质数判定算法：试除法和素数筛法。

1. 试除法（Trial Division）：

试除法是最朴素的质数判定算法。它通过逐个判断待判定数 n 是否能被小于 n 的所有数整除来判断 n 是否为质数。具体步骤如下：

- 若 n 小于 2，则 n 不是质数；

- 从2开始，逐个检查从2到 n-1 的所有整数 i，判断 n 是否能被 i 整除；

- 若 n 能被任意一个 i 整除，则 n 不是质数；

- 若 n 不能被任何一个 i 整除，则 n 是质数。

实现代码如下：

   def is_prime(n):
       if n < 2:
           return False
       for i in range(2, n):
           if n % i == 0:
               return False
       return True
   

试除法的时间复杂度为 O(n)，其中 n 是待判定的数。

2. 素数筛法（Sieve of Eratosthenes）：

素数筛法是一种更高效的质数判定算法。它通过逐个标记去除所有质数的倍数来筛选出质数。具体步骤如下：

- 初始化一个长度为 n+1 的布尔数组 is_prime，将所有元素初始化为 True；

- 将 is_prime[0] 和 is_prime[1] 设置为 False，因为它们不是质数；

- 对于从 2 到 sqrt(n) 的每个数 i，若 is_prime[i] 为 True，则将从 i*i 开始，以 i 为间隔的所有数都标记为 False，因为它们是 i 的倍数，不是质数；

- 遍历 is_prime 数组，如果某个位置值仍为 True，则该位置对应的数是质数。

实现代码如下：

   import math
   def is_prime(n):
       if n < 2:
           return False
       is_prime = [True] * (n+1)
       is_prime[0] = is_prime[1] = False
       for i in range(2, int(math.sqrt(n)) + 1):
           if is_prime[i]:
               for j in range(i*i, n+1, i):
                   is_prime[j] = False
       return is_prime[n]

   

素数筛法的时间复杂度为 O(n log(logn))，其中 n 是待判定的数。

无论是试除法还是素数筛法，都可以用来判断一个数是否为质数。然而，素数筛法相对于试除法来说更加高效，特别是在需要判断大量数是否为质数的情况下。