如何判断一个数是否是质数？-Python教程-PHP中文网

如何判断一个数是否是质数？

betcha

发布： 2025-09-04 16:51:02

原创

1153人浏览过

判断一个数是否是质数，核心是检查其是否有除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

登录后复制

。现在我们考虑

登录后复制

和

登录后复制

的大小关系：

如果
```
a = b
```
登录后复制
，那么
```
n = a * a
```
登录后复制
，所以
```
a = sqrt(n)
```
登录后复制
。
如果
```
a < sqrt(n)
```
登录后复制
，那么为了让
```
a * b = n
```
登录后复制
，
```
b
```
登录后复制
就必须大于
```
sqrt(n)
```
登录后复制
。
反过来，如果
```
a > sqrt(n)
```
登录后复制
，那么
```
b
```
登录后复制
就必须小于
```
sqrt(n)
```
登录后复制
。

你看，这中间的逻辑就很清晰了：如果

登录后复制

有一个大于其平方根的因子，那么它必然会有一个小于或等于其平方根的因子。反之亦然。所以，我们只需要检查到

sqrt(n)

登录后复制

就足够了。如果在这个范围里找不到任何因子，那么大于

sqrt(n)

登录后复制

的范围里也肯定不会有独立的因子存在（因为如果有，就必然会有一个对应的、小于或等于

sqrt(n)

登录后复制

的因子已经被我们检查过了）。这个优化将我们的检查范围从

登录后复制

大幅缩小到了

sqrt(n)

登录后复制

，对于大数来说，这效率提升可不是一点半点。比如，检查一个100位的数，如果没有这个优化，你需要检查大约

10^99

登录后复制

次，而有了它，只需要检查大约

10^49

登录后复制

次，虽然还是很大，但已经是一个数量级的飞跃了。当然，对于特别大的数，即使是

sqrt(n)

登录后复制

的复杂度也还是太高了，那又是另一个故事了。

对于超大数，试除法还高效吗？除了试除法，还有哪些更快的质数判断算法？

坦白说，对于非常大的数，比如在密码学中常见的几百位甚至上千位的数，我们刚才讨论的试除法就不够用了。虽然

sqrt(n)

登录后复制

看起来很小，但当

登录后复制

本身是

10^100

登录后复制

甚至更大时，

sqrt(n)

登录后复制

仍然是一个天文数字，遍历起来依然是痴人说梦。

这时候，我们需要更“聪明”的算法。其中一个非常著名的就是 Miller-Rabin 质数测试。它是一个概率性的质数测试算法，这意味着它在绝大多数情况下都能给出正确答案，但有极小的概率会出错（把合数误判为质数）。不过，通过增加测试轮数，这个出错的概率可以变得非常非常小，小到可以忽略不计。

即构数智人

即构数智人是由即构科技推出的AI虚拟数字人视频创作平台，支持数字人形象定制、短视频创作、数字人直播等。

查看详情

Miller-Rabin 的核心思想是基于费马小定理和二次探测定理。它不是去寻找因子，而是去验证一个数是否满足质数的一些必要条件。如果一个数不满足这些条件，那它肯定不是质数；如果满足了，那它“很可能”是质数。对于实际应用，比如RSA加密，这种“很可能”的质数已经足够安全了。

除了Miller-Rabin，还有一些确定性的质数测试算法，比如AKS质数测试（Agrawal-Kayal-Saxena），它在理论上是多项式时间复杂度的，但在实际应用中，对于我们日常遇到的“大数”，Miller-Rabin 往往更快。当然，这些算法的实现比试除法复杂得多，通常需要用到模幂运算等数论知识。

所以，如果你只是想判断一个几位到十几位的数，试除法足够了。但如果你面对的是上百位甚至上千位的数，那就要考虑 Miller-Rabin 这样的高级算法了。这就像你要去隔壁商店买瓶水，走路就行；但如果你要去另一个城市，那肯定得坐飞机或高铁，而不是继续走路。

在实现质数判断时，有哪些常见的误区和实用优化思路？

在实际编写代码时，哪怕是最简单的试除法，也容易掉进一些小“坑”里，或者忽略一些可以提升性能的细节。

常见的误区：

忘记处理
1
登录后复制
和
2
登录后复制
：很多人会直接从
```
i = 2
```
登录后复制
开始循环，但这样一来，
```
1
```
登录后复制
会被错误地判断为质数（因为它没有任何数能整除它），而
```
2
```
登录后复制
可能会因为
```
n % 2 == 0
```
登录后复制
的

以上就是如何判断一个数是否是质数？的详细内容，更多请关注php中文网其它相关文章！