問題1.22

とりあえずがんばってみたけど…
runtimeがchez schemeにないのでこちらを参考にして、gaucheで実行してみる。

僕の解答

指定範囲内のcount個の素数を検索する関数を定義。

(define (runtime)
	(use srfi-11)
	(let-values (((a b) (sys-gettimeofday)))
		    (+ (* a 1000000) b)))

(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 (square n)
	(* n n))

(define (prime? n)
	(= n (smallest-divisor n)))

(define (timed-prime-test n)
	(display n)
	(start-prime-test n (runtime))
	(newline))

(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 (search-for-primes n max count)
	(if (and (> count 0) (<= n max))
	    (cond ((prime? n)
		   (timed-prime-test n)
		   (search-for-primes (+ n 1) max (- count 1)))
		  (else
		   (search-for-primes (+ n 1) max count)))))

(search-for-primes 1000    10000    3)
(search-for-primes 10000   100000   3)
(search-for-primes 100000  1000000  3)
(search-for-primes 1000000 10000000 3)

で、実行すると…


1009 *** 0
1013 *** 0
1019 *** 0
10007 *** 0
10009 *** 0
10037 *** 0
100003 *** 0
100019 *** 0
100043 *** 0
1000003 *** 1000
1000033 *** 0
1000037 *** 1000
…むー。
よく分からないので組み込み関数(っぽい感じの)timeを使ってみる。

(define (search-for-primes n max count)
	(if (and (> count 0) (<= n max))
	    (cond ((prime? n)
		   (display n)
		   (newline)
		   (time (prime? n))
		   (search-for-primes (+ n 1) max (- count 1)))
		  (else
		   (search-for-primes (+ n 1) max count)))))


1009
;(time (prime? n))
; real 0.000
; user 0.000
; sys 0.000
1013
;(time (prime? n))
; real 0.001
; user 0.000
; sys 0.000
1019
;(time (prime? n))
; real 0.000
; user 0.000
; sys 0.000
10007
;(time (prime? n))
; real 0.000
; user 0.000
; sys 0.000
10009
;(time (prime? n))
; real 0.000
; user 0.000
; sys 0.000
10037
;(time (prime? n))
; real 0.000
; user 0.000
; sys 0.000
100003
;(time (prime? n))
; real 0.001
; user 0.000
; sys 0.000
100019
;(time (prime? n))
; real 0.000
; user 0.000
; sys 0.000
100043
;(time (prime? n))
; real 0.000
; user 0.000
; sys 0.000
1000003
;(time (prime? n))
; real 0.000
; user 0.000
; sys 0.000
1000033
;(time (prime? n))
; real 0.001
; user 0.000
; sys 0.000
1000037
;(time (prime? n))
; real 0.001
; user 0.000
; sys 0.000
…えー…。

所感

実装に依存した話は、きびしーなぁ…。
とことん調べるのがベストなんだろうけど。