問題1.24

SICP

僕の解答

とりあえず実装。
試行回数は10回としてみる。

(use srfi-27)
(define random random-integer)

(define (runtime)
	(- (time->seconds (current-time)) 1136041200))

(define (square n)
	(* n n))

(define (expmod base exp m)
	(cond ((= exp 0) 1)
	      ((even? exp)
	       (remainder (square (expmod base (/ exp 2) m))
			  m))
	      (else
	       (remainder (* base (expmod base (- exp 1) m))
			  m))))

(define (fermat-test n)
	(define (try-it a)
		(= (expmod a n n) a))
	(try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
	(cond ((= times 0) #t)
	      ((fermat-test n) (fast-prime? n (- times 1)))
	      (else #f)))

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

(define (start-prime-test n start-time)
	(if (fast-prime? n 10)
	    (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 ((fast-prime? n 10)
		   (timed-prime-test n)
		   (search-for-primes (+ n 1) max (- count 1)))
		  (else
		   (search-for-primes (+ n 1) max count)))))

(define (next n)
	(if (= n 2) 3
	  (+ n 2)))

(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.0

1013 *** 0.0

1019 *** 0.0

10007 *** 9.999275207519531e-4

10009 *** 0.0

10037 *** 0.0

100003 *** 0.0

100019 *** 0.0

100043 *** 0.0

1000003 *** 0.0

1000033 *** 9.999275207519531e-4

1000037 *** 0.0
ベンチマークは無理…(;_;

解答例