diff options
author | Bryan Newbold <bnewbold@robocracy.org> | 2017-02-20 00:05:27 -0800 |
---|---|---|
committer | Bryan Newbold <bnewbold@robocracy.org> | 2017-02-20 00:05:27 -0800 |
commit | fa3f23105ddcf07c5900de47f19af43d1db1b597 (patch) | |
tree | b2c6cce6b97698098f50cbc78c23fdc0f8d401ab /factor.scm | |
parent | f24b9140d6f74804d5599ec225717d38ca443813 (diff) | |
download | slib-fa3f23105ddcf07c5900de47f19af43d1db1b597.tar.gz slib-fa3f23105ddcf07c5900de47f19af43d1db1b597.zip |
Import Upstream version 2c3upstream/2c3
Diffstat (limited to 'factor.scm')
-rw-r--r-- | factor.scm | 33 |
1 files changed, 18 insertions, 15 deletions
@@ -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?) |