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.
49 lines
1.3 KiB
49 lines
1.3 KiB
;; chicken scheme doesn't provide a (runtime) primitive, |
|
;; and (current-milliseconds) is the best i could get |
|
|
|
(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 (next test-divisor))))) |
|
|
|
(define (divides? a b) |
|
(= (remainder b a) 0)) |
|
|
|
(define (next a) |
|
(if (= 2 a) |
|
3 |
|
(+ a 2))) |
|
|
|
(define (prime? n) |
|
(= n (smallest-divisor n))) |
|
|
|
(define (timed-prime-test n) |
|
(start-prime-test n (current-milliseconds))) |
|
|
|
(define (start-prime-test n start-time) |
|
(if (prime? n) |
|
(report-prime n (- (current-milliseconds) start-time)))) |
|
|
|
(define (search-for-primes min-bound max-bound) |
|
(define (iter cur max-bound) |
|
(if (<= cur max-bound) (timed-prime-test cur)) |
|
(if (<= cur max-bound) (iter (+ cur 2) max-bound))) |
|
(iter (if (even? min-bound) (+ min-bound 1) min-bound) |
|
(if (even? max-bound) (+ max-bound 1) max-bound))) |
|
|
|
(define (report-prime n elapsed-time) |
|
(display n) |
|
(display " *** ") |
|
(display elapsed-time) |
|
(newline)) |
|
|
|
;; 1009 1.0, 1013 0.0, 1019 0.0 |
|
;; 10007 0.0, 10009 0.0, 10037 0.0 |
|
;; 100003 1.0, 100019 0.0, 100043 0.0 |
|
;; 1000003 2.0, 1000033 2.0, 1000037 2.0
|
|
|