codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
; 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)))
Private
[
?
]
Run code
Submit