From fa3f23105ddcf07c5900de47f19af43d1db1b597 Mon Sep 17 00:00:00 2001 From: Bryan Newbold Date: Mon, 20 Feb 2017 00:05:27 -0800 Subject: Import Upstream version 2c3 --- factor.scm | 33 ++++++++++++++++++--------------- 1 file changed, 18 insertions(+), 15 deletions(-) (limited to 'factor.scm') diff --git a/factor.scm b/factor.scm index 6d7b38d..a5c7b44 100644 --- a/factor.scm +++ b/factor.scm @@ -130,21 +130,24 @@ (prime:f u (+ v b) (+ b b) (quotient (- n u) 2)))))) (define (prime:factor m) - (if - (negative? m) (cons -1 (prime:factor (- m))) - (let* ((s (gcd m prime:product)) - (r (quotient m s))) - (if (even? s) - (append - (if (= 1 r) '() (prime:factor r)) - (cons 2 (let ((s/2 (quotient s 2))) - (if (= s/2 1) '() - (or (prime:f 1 1 2 (quotient (- s/2 1) 2)) - (list s/2)))))) - (if (= 1 s) (or (prime:f 1 1 2 (quotient (- m 1) 2)) (list m)) - (append (if (= 1 r) '() - (or (prime:f 1 1 2 (quotient (- r 1) 2)) (list r))) - (or (prime:f 1 1 2 (quotient (- s 1) 2)) (list s)))))))) + (case m + ((-1 0 1) (list m)) + (else + (if (negative? m) (cons -1 (prime:factor (- m))) + (let* ((s (gcd m prime:product)) + (r (quotient m s))) + (if (even? s) + (append + (if (= 1 r) '() (prime:factor r)) + (cons 2 (let ((s/2 (quotient s 2))) + (if (= s/2 1) '() + (or (prime:f 1 1 2 (quotient (- s/2 1) 2)) + (list s/2)))))) + (if (= 1 s) (or (prime:f 1 1 2 (quotient (- m 1) 2)) (list m)) + (append + (if (= 1 r) '() + (or (prime:f 1 1 2 (quotient (- r 1) 2)) (list r))) + (or (prime:f 1 1 2 (quotient (- s 1) 2)) (list s)))))))))) (define jacobi-symbol prime:jacobi-symbol) (define prime? prime:prime?) -- cgit v1.2.3