2015/10/07

# 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倍となっているので予想通りと言える．

© 2022 wat-aro