H1：SICP 中判断素数的方法及相关测试

• H2：朴素素数判定方法

  • 若数 n 除 1 以外的最小因数是它自己，则 n 是素数，代码为(define (smallest-divisor n) (find-divisor n 2))等。
  • 此方法阶为 O(n)，速度较慢。

• H2：费马小定理及相关合数

  • 若 n 是素数，对任意 a（如 561、1105 等钉子户合数），在费马测试中可冒充素数，100000000 以内有 255 个 Carmichael 数。

• H2：Miller-Rabin 测试法

  • 基于费马小定理变形，若 n 是素数，对任何 a < n，a^(n - 1) ≡ 1(mod n)。
  • 执行 Fermat 测试的平方步骤时检查是否有“1 mod n 的非平凡平方根”，若存在则 n 不是素数，代码为(define (mr-test n) (define (try-it a) (= 1 (mr-expmod a (- n 1) n))) (try-it (+ 1 (random (- n 1)))))等。

• H2：不同方法在不同区间的测试结果

  • 在[1000, 1100]等区间，常规方法、因数 2 优化版本、Miller-Rabin 测试法时间均为 1ms。
  • 在更大区间如[1000000, 1000100]，常规方法 1337ms，因数 2 优化版本 830ms，Miller-Rabin 测试法 1ms。
  • C 语言版本在[2, 10000]区间，Normal 方法 10ms，Fermat 方法 24ms，Miller-Rabin 方法 28ms；在[200000, 1000000]区间，Normal 方法 3088ms，Fermat 方法 824ms，Miller-Rabin 方法 959ms。
  • gprof 分析结果显示，is_prime(int)占比较大，fermat_expmod(long, long, long)等函数也有一定耗时。

• H2：猜测及改进方向

  • 当 n 较小时 C 语言处理普通递归花销大导致效果不好。
  • 若将算法改成迭代形式或尾递归形式（gcc 可优化），效果可能更明显。