[ create a new paste ] login | about

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

programmingpraxis - Scheme, pasted on Jan 29:
; proving primality

(define (expm b e m)
  (define (m* x y) (modulo (* x y) m))
  (cond ((zero? e) 1)
        ((even? e) (expm (m* b b) (/ e 2) m))
        (else (m* b (expm (m* b b) (/ (- e 1) 2) m)))))

(define (td-factors n)
  (let loop ((n n) (x 2) (fs '()))
    (cond ((< n (* x x)) (reverse (cons n fs)))
          ((zero? (modulo n x)) (loop (/ n x) x (cons x fs)))
          (else (loop n (+ x 1) fs)))))

(define (prime? n)
  (let ((n-1 (- n 1)))
    (let loop ((b 2) (qs (td-factors n-1)))
      (cond ((not (= (expm b n-1 n) 1)) (loop (+ b 1) qs))
            ((null? qs) #f)
            ((not (= (expm b (/ n-1 (car qs)) n) 1)) #t)
            (else (loop b (cdr qs)))))))

(display (prime? (- (expt 2 89) 1)))


Output:
1
#t


Create a new paste based on this one


Comments: