判断一个数是否是质数，核心是检查其是否有除1和自身外的因子，只需试除到平方根即可，因若存在大于平方根的因子，则必有对应的小于等于平方根的因子，故只需用2和3到√n的奇数试除，可高效判断。
判断一个数是否是质数，核心在于检查它除了1和自身之外，是否还有其他正整数因子。最直观的方法就是尝试用2到这个数平方根之间的所有整数去除它，如果都不能整除，那它就是质数。
说起来简单，但真正动手写代码时，还是有些细节需要考虑的。 首先，我们得明确质数的定义：大于1的自然数，且除了1和它本身，不能被其他自然数整除。所以，小于等于1的数肯定不是质数。2是最小的质数，也是唯一的偶数质数。 对于任何一个大于2的偶数，它显然可以被2整除，所以也不是质数。这样一来，我们只需要关注奇数了。
具体的流程可以这样来：
-
处理特殊情况：
- 如果
n <= 1
，直接返回False
(不是质数)。 - 如果
n == 2
，直接返回True
(是质数)。 - 如果
n > 2
且n
是偶数，直接返回False
(不是质数)。
- 如果
-
核心循环：
- 从
i = 3
开始，每次递增2（只检查奇数）。 - 循环条件是
i * i <= n
(或者i <= sqrt(n)
，但乘法通常比开方快一点，且避免浮点数精度问题)。 - 在循环中，如果
n % i == 0
，说明n
有除了1和自身以外的因子i
，那么n
就不是质数，直接返回False
。
- 从
-
最终判断：
- 如果循环结束了，都没有找到任何因子，那么
n
就是质数，返回True
。
- 如果循环结束了，都没有找到任何因子，那么
这是一个简单的Python实现示例：
import math
def is_prime(n):
if n <= 1:
return False
if n == 2:
return True
if n % 2 == 0: # 排除所有大于2的偶数
return False
# 只需要检查到n的平方根
# 步长为2，只检查奇数
for i in range(3, int(math.sqrt(n)) + 1, 2):
if n % i == 0:
return False
return True
# 示例测试
# print(is_prime(1)) # False
# print(is_prime(2)) # True
# print(is_prime(3)) # True
# print(is_prime(4)) # False
# print(is_prime(17)) # True
# print(is_prime(997)) # True
# print(is_prime(1000000007)) # True (这是一个大质数)
# print(is_prime(10000000019)) # True
# print(is_prime(10000000021)) # False (可以被3整除)这个方法被称为“试除法”，它的逻辑非常直接，也很好理解。
为什么判断质数只需要检查到平方根？这个优化背后的数学原理是什么？
这确实是一个非常巧妙且关键的优化，我第一次理解的时候也觉得挺“啊哈！”的。我们来稍微推导一下。 假设一个合数
n，它可以被分解成两个因子
a和
b的乘积，即
n = a * b。 现在我们考虑
a和
b的大小关系：
- 如果
a = b
，那么n = a * a
，所以a = sqrt(n)
。 - 如果
a < sqrt(n)
，那么为了让a * b = n
，b
就必须大于sqrt(n)
。 - 反过来，如果
a > sqrt(n)
，那么b
就必须小于sqrt(n)
。
你看，这中间的逻辑就很清晰了：如果
n有一个大于其平方根的因子，那么它必然会有一个小于或等于其平方根的因子。反之亦然。所以，我们只需要检查到
sqrt(n)就足够了。如果在这个范围里找不到任何因子，那么大于
sqrt(n)的范围里也肯定不会有独立的因子存在（因为如果有，就必然会有一个对应的、小于或等于
sqrt(n)的因子已经被我们检查过了）。 这个优化将我们的检查范围从
n大幅缩小到了
sqrt(n)，对于大数来说，这效率提升可不是一点半点。比如，检查一个100位的数，如果没有这个优化，你需要检查大约
10^99次，而有了它，只需要检查大约
10^49次，虽然还是很大，但已经是一个数量级的飞跃了。当然，对于特别大的数，即使是
sqrt(n)的复杂度也还是太高了，那又是另一个故事了。
对于超大数，试除法还高效吗？除了试除法，还有哪些更快的质数判断算法？
坦白说，对于非常大的数，比如在密码学中常见的几百位甚至上千位的数，我们刚才讨论的试除法就不够用了。虽然
sqrt(n)看起来很小，但当
n本身是
10^100甚至更大时，
sqrt(n)仍然是一个天文数字，遍历起来依然是痴人说梦。
这时候，我们需要更“聪明”的算法。其中一个非常著名的就是 Miller-Rabin 质数测试。它是一个概率性的质数测试算法，这意味着它在绝大多数情况下都能给出正确答案，但有极小的概率会出错（把合数误判为质数）。不过，通过增加测试轮数，这个出错的概率可以变得非常非常小，小到可以忽略不计。
Miller-Rabin 的核心思想是基于费马小定理和二次探测定理。它不是去寻找因子，而是去验证一个数是否满足质数的一些必要条件。如果一个数不满足这些条件，那它肯定不是质数；如果满足了，那它“很可能”是质数。对于实际应用，比如RSA加密，这种“很可能”的质数已经足够安全了。
除了Miller-Rabin，还有一些确定性的质数测试算法，比如AKS质数测试（Agrawal-Kayal-Saxena），它在理论上是多项式时间复杂度的，但在实际应用中，对于我们日常遇到的“大数”，Miller-Rabin 往往更快。当然，这些算法的实现比试除法复杂得多，通常需要用到模幂运算等数论知识。
所以，如果你只是想判断一个几位到十几位的数，试除法足够了。但如果你面对的是上百位甚至上千位的数，那就要考虑 Miller-Rabin 这样的高级算法了。这就像你要去隔壁商店买瓶水，走路就行；但如果你要去另一个城市，那肯定得坐飞机或高铁，而不是继续走路。
在实现质数判断时，有哪些常见的误区和实用优化思路？
在实际编写代码时，哪怕是最简单的试除法，也容易掉进一些小“坑”里，或者忽略一些可以提升性能的细节。
常见的误区：
-
忘记处理
1
和2
： 很多人会直接从i = 2
开始循环，但这样一来，1
会被错误地判断为质数（因为它没有任何数能整除它），而2
可能会因为n % 2 == 0
的
