费马分解法极限

这个 (< limit y) 不需要检查,因为在最坏的情况下,算法最终会找到此解决方案:

X = n + 2

Y = n

然后返回1。

看穿 算法C ,看起来问题在于递归步骤,它在任何时候都有效地跳过步骤c4。 r < 0 ,因为 x 不是递增的 r 只有 y .

使用符号 a , b 和 R 从1998年版第2卷(ISBN 0-201-89684-2)开始,方案版本如下:

(define (factor n) 
  (let ((x (inexact->exact (floor (sqrt n)))))
    (factor-inner (+ (* x 2) 1)
                  1
                  (- (* x x) n))))

(define (factor-inner a b r)
  (cond ((= r 0) (/ (- a b) 2))
        ((< 0 r) (factor-inner a       (+ b 2) (- r b)))
        (else    (factor-inner (+ a 2) (+ b 2) (- r (- a b))))))

编辑 补充:基本上,我们正在做一个反复检查

r <- ((a - b) / 2)*((a + b - 2)/2) - N

是0,我们只是通过跟踪 R 当我们增加 一 或 乙 . 如果我们准备 乙 到 b+2 在表达式中 R 上面,它相当于减少 R 根据 乙 ,这就是为什么在算法的步骤c4中两者并行完成的原因。我鼓励你展开上面的代数表达式,并说服自己这是真的。

只要 r > 0 ,您希望继续减小它以找到 乙 ,所以你继续重复步骤c4。但是,如果你超调,并且 R<0 ,你需要增加它。你通过增加 一 ,因为 一 2等于减少 R 根据 一 ,如步骤c3所示。你将永远拥有 a > b ,所以越来越多 R 通过 一 在步骤c3中自动生成 R 再次肯定,所以你直接进入步骤C4。

也很容易证明 A & B . 我们从 一 明显大于 乙 ,如果我们增加 乙 以至于 b = a - 2 我们有

N = (a - (a - 2))/2 * ((a + (a - 2) - 2)/2 = 1 * (a - 2)

这意味着 N 是质数,因为它的最大因子小于 sqrt(N) 为1,并且算法已终止。