素数判断

素数（质数）是大于 1 且只有 1 和自身两个因数的自然数：2、3、5、7、11、13……2 是唯一的偶素数。合数则可分解为更小整数的乘积。判断 n 是否素数只需试除到 √n——若 n = a×b 且 a ≤ b，则 a ≤ √n，所以 √n 以内找不到因数就必是素数。97：试 2、3、5、7（都除不尽），√97 < 10，判定为素数。

素数定理揭示它们的分布：不超过 x 的素数约有 x/ln(x) 个——100 以内 25 个、1000 以内 168 个、越往大越稀疏但永不枯竭（欧几里得 2300 年前就证明了素数无穷：假设有限个素数，乘积加 1 必含新素因子，矛盾）。孪生素数（差为 2，如 11 与 13、101 与 103）是否有无穷多对，至今仍是未解难题（张益唐 2013 年把间隙压到 7000 万以内，震惊数坛）。

素数的现代王座在密码学：RSA 把两个几百位的大素数相乘公开，分解回素因子需要超算跑宇宙年龄——"乘起来容易、拆开难"的单向性保护着全球网银与通信。大素数检测用 Miller-Rabin 概率算法（几轮测试把误判率压到 2⁻⁸⁰），生成密钥对只需毫秒。

素数是整数的「原子」——算术基本定理说每个大于 1 的整数都唯一分解为素数之积（素因数分解计算器 做的正是这件事）。欧几里得两千多年前就证明了素数无穷：假设素数有限，把它们全乘起来加 1，新数不被任何已知素数整除，矛盾。但「无穷」不等于「好找」：素数定理告诉我们 n 附近的素数密度约为 1 ÷ ln n，百万附近每 14 个数才摊上一个素数，十亿附近每 21 个才一个——越往大越稀疏，却永不枯竭。

大数判素数是密码学的地基。试除法对几十位的数就失效了，工程上用 Miller-Rabin 概率性测试：随机选几个「证人」基底做模幂检验，每轮把合数误判为素数的概率压到 1/4 以下，做 20 轮后误判概率不到万亿分之一，而速度比确定性测试快几个数量级。RSA 密钥对正是靠「快速找两个 1024 位素数、但分解其乘积极难」的不对称性立足——想亲手算 RSA 分解的难度 可以从两位数试起。