[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/Exr2kj9L    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on May 17:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
; fermat's method

(define (isqrt n)
  (let loop ((x n) (y (quotient (+ n 1) 2)))
    (if (<= 0 (- y x) 1) x
      (loop y (quotient (+ y (quotient n y)) 2)))))

(define (factors n)
  (if (even? n) (cons 2 (factors (/ n 2)))
    (let ((s (+ (isqrt n) 1)))
      (let loop ((u (+ s s 1)) (v 1) (r (- (* s s) n)))
        (cond ((positive? r) (loop u (+ v 2) (- r v)))
              ((negative? r) (loop (+ u 2) v (+ r u)))
              ((= (- u v) 2) (list (/ (+ u v -2) 2)))
              (else (append (factors (/ (+ u v -2) 2))
                            (factors (/ (- u v) 2)))))))))

(display (factors 600851475143))


Output:
1
(1471 839 6857 71)


Create a new paste based on this one


Comments: