SICP 問題1.22
(define (timed-prime-test n) (newline) (display n) (start-prime-test n (runtime))) (define (start-prime-test n start-time) (if (prime? n) (report-prime (- (runtime) start-time)))) (define (report-prime elapsed-time) (display " *** ") (display elapsed-time)) (define (runtime) (use srfi-11) (let-values (((a b) (sys-gettimeofday))) (+ (* a 1000000) b)))
以上を使って指定範囲の連続する奇数について素数性を調べる手続き手続きを書く.
(define (search-for-primes start end) (define (iter start end) (cond ((> start end) (newline)) ((prime? start) (and (timed-prime-test start) (iter (+ 2 start) end))) (else (iter (+ 2 start) end)))) (if (odd? start) (iter start end) (iter (+ 1 start) end)))
gosh> (search-for-primes 1000 1100) 1009 *** 6 1013 *** 6 1019 *** 5 1021 *** 5 1031 *** 6 1033 *** 6 1039 *** 6 1049 *** 6 1051 *** 5 1061 *** 6 1063 *** 6 1069 *** 5 1087 *** 6 1091 *** 6 1093 *** 6 1097 *** 6 #<undef> gosh> (search-for-primes 10000 10100) 10007 *** 28 10009 *** 17 10037 *** 17 10039 *** 17 10061 *** 17 10067 *** 17 10069 *** 17 10079 *** 18 10091 *** 17 10093 *** 17 10099 *** 18 #<undef> gosh> (search-for-primes 100000 100100) 100003 *** 85 100019 *** 55 100043 *** 55 100049 *** 55 100057 *** 54 100069 *** 54 #<undef> gosh> (search-for-primes 1000000 1000100) 1000003 *** 195 1000033 *** 172 1000037 *** 172 1000039 *** 172 1000081 *** 176 1000099 *** 176 #<undef>
nが100倍になると処理時間は概ね10倍となっているので予想通りと言える.