试除法判素数

请实现 solution(n: int) -> bool，在 n 是素数时返回 True，否则返回 False。素数是指大于 1、且只有 1 和自身两个正因子的整数。按惯例，0 和 1 不是素数。

期望做法是**试除到 sqrt(n)**：对每个候选因子 d，从 2 到 floor(sqrt(n))，检查 d 是否整除 n；只要有一个能整除，n 就是合数。平方根上界源于：任何非平凡分解 n = a * b（a <= b）必然满足 a <= sqrt(n)，所以只找较小的那个因子就够了。

干净的实现模板是：先把 n < 2、n = 2、n = 3、以及偶数 n 几种特例处理掉，再让奇数 d = 3, 5, 7, ... 在 d * d <= n 范围内迭代。

Examples

solution(2) 返回 True。最小的素数；n == 2 这个特例必须在偶数剪枝之前命中，否则会被错杀。

solution(9999991) 返回 True。是不超过 10⁷ 的最大素数。循环以 d = 3, 5, 7, ..., 3161 迭代（约 1581 个奇数候选，因为 3163² = 10004569 > 9999991），没有一个能整除 n，故返回 True。

solution(25) 返回 False。25 = 5 × 5，当 d = 5、d * d = 25 <= n 时，n % d == 0 触发，函数返回 False。这个例子说明为什么循环条件要写成 d * d <= n（不能是 <）：素数的平方恰是平方根本身就是整数因子的输入。

签名见 stubs/stub.py。

Practical context

素性测试是公钥密码学的基础原语。RSA、Diffie-Hellman、DSA、椭圆曲线密钥生成都需要造出大素数（典型是 1024 或 2048 位），标准流水线是：先随机抽一个目标位长的奇整数，用试除法对前几千个小素数过一遍（这一步可以便宜地杀掉约 80% 的候选），然后跑 Miller-Rabin 概率测试，跑足够多的随机见证把假素数概率压到 2^-128 以下。试除到 sqrt(n)——也就是本题里的算法——是小素数筛预计算时的参考实现，同时也是 n 不超过约 10⁹ 时的确定性金标准（这个范围内 Miller-Rabin 配 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} 这套见证集已被证明完全正确）。本题里 sqrt 上界这条捷径——O(n) 和 O(sqrt(n)) 的差距——正是让 RSA 密钥生成可行的核心：1024 位下，朴素试除会比宇宙年龄还长，而「先小素数筛、后 Miller-Rabin」的结构化流水线只要几秒。除了密码学，素性测试还在哈希表选容量（用素数大小避免聚簇）、编码理论里的多项式模数选择（BCH、Reed-Solomon）、以及计算代数系统里的 Lehmer/AKS 算法中起作用。把这里的 d * d <= n 边界和奇数轮子吃透，就抓住了能放大到 4096 位 RSA 的同一套结构。