Python实现高效质数判断算法详解

好的，我们先来一步步分析这个问题。 ## 🎯 问题理解 我们需要判断一个整数 `n` 是否为质数。 质数的定义是：大于 1 的自然数，并且只能被 1 和它本身整除。 **边界情况**： - 如果 `n <= 1`，则不是质数。 - 如果 `n == 2`，是质数（最小的质数）。 - 如果 `n` 是偶数且大于 2，则不是质数。 - 对于奇数 `n`，只需要检查从 3 到 `sqrt(n)` 之间的奇数是否能整除 `n`。 ## 🧮 算法设计 1. 如果 `n <= 1`，直接输出 `"not prime"`。 2. 如果 `n == 2`，输出 `"prime"`。 3. 如果 `n % 2 == 0`，输出 `"not prime"`。 4. 否则，从 `i = 3` 开始，循环到 `sqrt(n)`，步长为 2（只检查奇数），如果发现 `n % i == 0`，则不是质数。 5. 如果循环结束都没有找到因数，则是质数。 ## 💻 代码实现（Python） ```python import math def is_prime(n): if n <= 1: return False if n == 2: return True if n % 2 == 0: return False # 只检查奇数因子 limit = int(math.isqrt(n)) # Python 3.8+ 可用 math.isqrt，更高效 for i in range(3, limit + 1, 2): if n % i == 0: return False return True # 主程序 if __name__ == "__main__": n = int(input().strip()) if is_prime(n): print("prime") else: print("not prime") ``` ## 📝 代码解释 - `math.isqrt(n)`：返回整数 `n` 的平方根向下取整，比 `int(math.sqrt(n))` 更高效且无浮点误差。 - 循环从 3 开始，步长为 2，只检查奇数因子，因为偶数已经在前面排除了。 - 时间复杂度约为 `O(sqrt(n))`，对于一般题目足够快。 ## ⚠️ 常见陷阱与优化 1. **不要检查到 `n-1`**：检查到 `sqrt(n)` 即可，因为如果 `n` 有一个大于 `sqrt(n)` 的因子，那么必定有一个小于 `sqrt(n)` 的因子与之对应。 2. **处理大数**：对于非常大的 `n`（如 `10^12` 以上），`O(sqrt(n))` 可能仍然较慢，此时可能需要更高级的算法（如 Miller-Rabin 素性测试），但本题一般不会要求那么高。 3. **输入范围**：注意题目是否说明 `n` 的范围，如果 `n` 可能为负数，则直接不是质数。 4. **特殊数字**：`2` 是唯一的偶质数，需要单独处理。 ## 🔧 测试样例 | 输入 | 输出 | 说明 | |------|------|------| | `1` | `not prime` | 小于等于 1 不是质数 | | `2` | `prime` | 最小的质数 | | `3` | `prime` | 质数 | | `4` | `not prime` | 可被 2 整除 | | `17` | `prime` | 质数 | | `100`| `not prime` | 可被多个数整除 | ## 🚀 进阶与扩展 - **预计算素数表**：如果需要频繁判断多个数，可以先用筛法（如埃拉托斯特尼筛法）生成素数表，然后查表判断。 - **Miller-Rabin 算法**：概率**性测试，极快，适用于大数。 - **确定性 Miller-Rabin**：对于 64 位整数，有确定的基组合可以保证正确性。 ## 📚 学习资源 - [素数判定 - OI Wiki](https://oi-wiki.org/math/number-theory/prime/) - [Python `math.isqrt` 文档](https://docs.python.org/3/library/math.html#math.isqrt) --- ######[AI写代码神器 | 985点数解答 | 2026-03-02 22:11:16]