数学

质数判断器（可检测1至1000万）

即时判断整数 N（1 至 1000 万）是否为质数。显示试除法步骤、前后质数及质因数分解。

前 100 个质数一览

#1–10 #2–11 #3–12 #4–13 #5–14 #6–15 #7–16 #8–17 #9–18 #10–19
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349
353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463
467 479 487 491 499 503 509 521 523 541

Tips

  • 质数是大于 1 的整数，除了 1 和它本身没有其他因数。序列为 2, 3, 5, 7, 11, 13, …
  • 最基本的质数检测方法是试除法：用 2 到 √N 的每个整数去除 N，若均不能整除则 N 为质数。
  • 1 不是质数。质数的定义要求"大于 1"。2 是唯一的偶质数。
  • 质数有无穷多个（欧几里得约于公元前 300 年证明）。质数在 n 附近的密度约为 1/ln(n)（质数定理）。

常见问题

2 除了 1 和它本身没有其他因数，因此按定义是质数。它也是唯一的偶质数——其他偶数都能被 2 整除。

质数的定义排除了 1（"大于 1 的整数"）。排除 1 是算术基本定理成立的必要条件：若 1 为质数，质因数分解将不唯一（例如 6 = 2 × 3 = 1 × 2 × 3 = 1¹⁰⁰ × 2 × 3）。

试除法的时间复杂度为 O(√N)。对于 N = 10,000,000，√N ≈ 3162，最多约需 3162 次除法。这对于交互使用已足够快速。
ツールくん

闲话 ― 质数为何如此重要

质数被称为"算术的原子"。算术基本定理指出，每个大于 1 的整数都有唯一的质因数分解，这意味着质数是所有整数的不可约基本构件。

现代RSA 加密——保障 HTTPS 通信和数字签名——依赖于质数。将两个大质数相乘很容易，但将乘积分解回质数即使对现代超级计算机也几乎不可能。质数支撑着互联网的安全。

同类工具