(wat-aro)

無職から有職者にランクアップしました

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