要写出 search-for-primes
函数,我们首先需要解决以下几个子问题:
n
,可以生成大于等于 n
的三个素数,或者更一般地,对于一个函数,给定它两个参数 n
和 count
,可以生成 count
个大于等于 n
的素数首先来解决问题一,函数 next-odd
接受一个参数 n
,生成跟随在 n
之后的第一个奇数:
;;; 22-next-odd.scm
(define (next-odd n)
(if (odd? n)
(+ 2 n)
(+ 1 n)))
测试 next-odd
,确保它满足了我们的需求:
1 ]=> (load "22-next-odd.scm")
;Loading "22-next-odd.scm"... done
;Value: next-odd
1 ]=> (next-odd 2)
;Value: 3
1 ]=> (next-odd 3)
;Value: 5
至于第二个问题,检测给定数是否为素数的函数,可以直接重用书本 33 页的 prime?
函数:
;;; p33-prime.scm
(load "p33-smallest-divisor.scm")
(define (prime? n)
(= n (smallest-divisor n)))
;;; p33-smallest-divisor.scm
(load "p33-divides.scm")
(load "p33-find-divisor.scm")
(define (smallest-divisor n)
(find-divisor n 2))
;;; p33-find-divisor.scm
(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)))))
;;; p33-divides.scm
(define (divides? a b)
(= (remainder b a) 0))
测试:
1 ]=> (load "p33-prime.scm")
;Loading "p33-prime.scm"...
; Loading "p33-smallest-divisor.scm"...
; Loading "p33-divides.scm"... done
; Loading "p33-find-divisor.scm"... done
; ... done
;... done
;Value: prime?
1 ]=> (prime? 7)
;Value: #t
1 ]=> (prime? 8)
;Value: #f
有了前面两个函数的支持,写出生成连续素数的函数就很直观了:首先使用 next-odd
生成一个奇数,然后使用 prime?
检查给定的奇数是否素数,一直这样计算下去,直到满足参数 count
指定的数量为止。
以下是 continue-primes
的定义:
;;; 22-continue-primes.scm
(load "p33-prime.scm")
(load "22-next-odd.scm")
(define (continue-primes n count)
(cond ((= count 0)
(display "are primes."))
((prime? n)
(display n)
(newline)
(continue-primes (next-odd n) (- count 1)))
(else
(continue-primes (next-odd n) count))))
continue-primes
函数会逐个逐个地打印出它找到的素数:
1 ]=> (load "22-continue-primes.scm")
;Loading "22-continue-primes.scm"...
; Loading "p33-prime.scm"...
; Loading "p33-smallest-divisor.scm"...
; Loading "p33-divides.scm"... done
; Loading "p33-find-divisor.scm"... done
; ... done
; ... done
; Loading "22-next-odd.scm"... done
;... done
;Value: continue-primes
1 ]=> (continue-primes 1000 3)
1009
1013
1019
are primes.
;Unspecified return value
1 ]=> (continue-primes 1000 10)
1009
1013
1019
1021
1031
1033
1039
1049
1051
1061
are primes.
;Unspecified return value
以上分别是大于等于 1000
的前三个素数,以及大于等于 1000
的前十个素数。
Note
在新版的 MIT Scheme 中, runtime
的返回结果已经不再是按微秒计算,而是按秒计算,这种格式对于我们要测量的程序来说太大了,为此,这里使用 real-time-clock 代替 runtime
,作为计时函数。
real-time-clock
以 ticks 为单位,返回 MIT Scheme 从开始到调用 real-time-clock
时所经过的时间,其中每个 ticks 为一毫秒:
1 ]=> (real-time-clock)
;Value: 624880
1 ]=> (real-time-clock)
;Value: 628007
要测量一个表达式的运行时间,我们可以在要测量的表达式的之前和之后分别添加一个 real-time-clock
函数,然后运行程序,两个 real-time-clock
之间的数值之差就是运行给定表达式所需的时间。
比如说,要测量函数 foo
的运行时间,可以执行以下函数:
(define (test-foo)
(let ((start-time (real-time-clock)))
(foo)
(- (real-time-clock) start-time)))
(test-foo)
调用的返回值就是 (foo)
运行所需的时间(以毫秒计算)。
现在,我们可以组合起前面的 continue-primes
函数和 real-time-clock
函数,写出题目要求的 search-for-primes
函数了,这个函数接受参数 n
,找出大于等于 n
的三个素数,并且返回寻找素数所需的时间作为函数的返回值:
;;; 22-search-for-primes.scm
(load "22-continue-primes.scm")
(define (search-for-primes n)
(let ((start-time (real-time-clock)))
(continue-primes n 3)
(- (real-time-clock) start-time)))
现在可以使用 search-for-primes
来完成题目指定的寻找素数的任务了:
1 ]=> (load "22-search-for-primes.scm")
;Loading "22-search-for-primes.scm"...
; Loading "22-continue-primes.scm"...
; Loading "p33-prime.scm"...
; Loading "p33-smallest-divisor.scm"...
; Loading "p33-divides.scm"... done
; Loading "p33-find-divisor.scm"... done
; ... done
; ... done
; Loading "22-next-odd.scm"... done
; ... done
;... done
;Value: search-for-primes
1 ]=> (search-for-primes 1000) ; 一千
1009
1013
1019
are primes.
;Value: 1
1 ]=> (search-for-primes 10000) ; 一万
10007
10009
10037
are primes.
;Value: 1
1 ]=> (search-for-primes 100000) ; 十万
100003
100019
100043
are primes.
;Value: 3
1 ]=> (search-for-primes 1000000) ; 一百万
1000003
1000033
1000037
are primes.
;Value: 7
可以看到,当 search-for-primes
的输入以 10 为倍数上升时,寻找素数所需的时间并不是严格地按照 \(\sqrt{10}\) 倍上升的,关于这个问题,我们留到 练习 1.24 再进行详细的说明。
Note
这里并没有使用书本给出的 timed-primes-test
等几个程序来写 search-for-primes
函数,因为使用它们的话反而会使程序变得复杂起来,所以没有必要多此一举。