作者：未知 来源：月光软件站 加入时间：2005-5-13　月光软件站

; ======================================================================
;
;          Structure and Interpretation of Computer Programs
;                  (trial answer to excercises)
;
;                  计算机程序的构造和解释(习题试解)
;
;                                             created: code17 02/28/05
;                                             modified:
; (保持内容完整不变前提下，可以任意转载)
; ======================================================================

;; SICP No.1.22

;; 在PLT Scheme中，测当前时间的函数使用current-inexact-millseconds，需要将
;; 原代码中对应的current-time替换

;; 因为需要控制寻找质数的数目，我们必须知道timed-prime-test是否成功，而在
;; 原来的函数定义中并没有将是否成功的信息作为结果返回。因此如果我们需要使用
;; timed-prime-test，我们需要原定义做一处的修改，如下
(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (current-inexact-milliseconds)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (current-inexact-milliseconds) start-time))
      #f))    ;; 这是唯一需要改的地方!

(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))


;; 主函数search-for-primes可简单定义为
(define (search-for-primes from n)
  (cond ((= n 0) (newline) (display "finish") (newline))
        ((even? from) (search-for-primes (+ from 1) n))
        ((timed-prime-test from) (search-for-primes (+ from 2) (- n 1)))
        (else (search-for-primes  (+ from 2) n))))


;; Test-it::
;;
;; 从运行时间测试可以看出，函数(prime? n)的时间复杂度确实近似地符合
;; [theta]([sqrt](n))的规律：
;; 其中n=1000左右的运行时间为0.039ms左右
;;     n=10000左右的运行时间为0.115左右
;;     n=100000左右的运行时间为0.363左右
;; t(10n) = [sqrt](10)t(n) = 3.1622776601683795
;;
;; Welcome to MzScheme version 209, Copyright (c) 2004 PLT Scheme, Inc.
;; > (search-for-primes 1000 3)
;;
;; 1001
;; 1003
;; 1005
;; 1007
;; 1009 *** 0.0390625
;; 1011
;; 1013 *** 0.039794921875
;; 1015
;; 1017
;; 1019 *** 0.0390625
;; finish
;;
;; > (search-for-primes 10000 3)
;;
;; 10001
;; 10003
;; 10005
;; 10007 *** 0.117919921875
;; 10009 *** 0.114990234375
;; 10011
;; 10013
;; 10015
;; 10017
;; 10019
;; 10021
;; 10023
;; 10025
;; 10027
;; 10029
;; 10031
;; 10033
;; 10035
;; 10037 *** 0.116943359375
;; finish
;;
;; > (search-for-primes 100000 3)
;;
;; 100001
;; 100003 *** 0.36376953125
;; 100005
;; 100007
;; 100009
;; 100011
;; 100013
;; 100015
;; 100017
;; 100019 *** 0.362060546875
;; 100021
;; 100023
;; 100025
;; 100027
;; 100029
;; 100031
;; 100033
;; 100035
;; 100037
;; 100039
;; 100041
;; 100043 *** 0.364990234375
;; finish
;; > 
;;

相关软件：