とりあえずがんばってみたけど…
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
解答例
所感
実装に依存した話は、きびしーなぁ…。
とことん調べるのがベストなんだろうけど。
