You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
37 lines
861 B
37 lines
861 B
(define (square x) |
|
(* x x)) |
|
|
|
(define (smallest-divisor n) |
|
(find-divisor n 2)) |
|
|
|
(define (find-divisor n test-divisor) |
|
(cond ((> (square test-divisor) n) n) |
|
((divides? test-divisor n) test-divisor) |
|
(else (find-divisor n (+ test-divisor 1))))) |
|
|
|
(define (divides? a b) |
|
(= (remainder b a) 0)) |
|
|
|
(define (prime? n) |
|
(= n (smallest-divisor n))) |
|
|
|
(define (exptmod base expn m) |
|
(cond ((= expn 0) 1) |
|
((even? expn) |
|
(remainder |
|
(square (exptmod base (/ expn 2) m)) |
|
m)) |
|
(else |
|
(remainder |
|
(* base (exptmod base (- expn 1) m)) |
|
m)))) |
|
|
|
(define (fermat-test n) |
|
(define (try-it a) |
|
(= (exptmod a n n) a)) |
|
(try-it (+ 1 (random (- n 1))))) |
|
|
|
(define (fast-prime? n times) |
|
(cond ((= times 0) #t) |
|
((fermat-test n) (fast-prime? n (- times 1))) |
|
(else #f)))
|
|
|