练习1.22
这道题中需要判断素数的部分书中都已经列出来了,但要求是要找出多个素数,因此我们要有一个能够不断求素数的函数。在C等语言中我们可以通过一个for循环来轻易地求出来,在Scheme中我们完全可以用迭代来实现这一功能。另外因为是要的素数,因此完全不用考虑偶数了。于是我们先来写一个不断求奇数的函数。
(define (odd-after-x x)
(if(odd? x)
(+ 2 x)
(+ 1 x)))
通过将偶数加1、奇数加2,轻易地求出了x之后的奇数。
判断素数的函数我们直接列出了:
(define (prime? n)
(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))
(= n (smallest-divisor n)))
下面我们利用这两个函数来定义一个不断产生素数的函数:
(define (prime-after-prime n count)
(cond((= count 0) (display “These are all prime numbers”))
((prime? n) (display n)
(newline)
(prime-after-prime (odd-after-x n) (- count1)))
(else (prime-after-prime (odd-after-x n)count))))
如此一来便能够按照书中的要求算出一千、一万等的3个最小的素数了,不过还不能计算所需时间。而要求时间,我们可以用real-time-clock,这在【Scheme归纳】7中有相关介绍。下面我们就来将计算时间的功能加入进去。
(define (get-time&prime n)
(let((start-time (real-time-clock)))
(prime-after-prime n 3)
由于题目中只要求求出3个最小的素数即可。
(- (real-time-clock) start-time)))
下面我们就来开始测试了:
(get-time&prime 1000)
1009
1013
1019
These are all prime numbers
;Value: 0
时间太短记为0了我也没办法,下面再来几组大的。
(get-time&prime 10000)
10007
10009
10037
These are all prime numbers
;Value: 0
还是0,莫非函数错了?再来一次。
(get-time&prime 100000)
100003
100019
100043
These are all prime numbers
;Value: 0
我也不知道为什么会这样了,用一百万测试的还是0,难度是i7的速度快?不过:
(get-time&prime 10000000)
10000019
10000079
10000103
These are all prime numbers
;Value: 15
继续,一亿用了47微秒,10亿用了157微秒。100亿、一千亿、一万亿用了672、1750、5156。一亿亿用了621890秒,3个最小的素数分别是10000000000000061、10000000000000069、10000000000000079。
后来在网上也看到相同的函数,而对方评论下说对方写错了。我再看看书中的内容发现果然如此,我也看错了,第36页上面说的是检查每个素数所需要的时间,应该是意味着每个素数都要有个时间吧?如是将函数改成了这样:
(define (get-time&prime n)
(let((start-time (real-time-clock)))
(define (prime-after-prime n count)
(cond ((= count 0) (display "These areall prime numbers."))
((prime? n) (display n)
(display (- (real-time-clock)start-time))
(newline)
(prime-after-prime(odd-after-x n) (- count 1)))
(else (prime-after-prime (odd-after-x n)count)))))
(prime-after-prime n 3)))
因为觉得返回更多的素数结果会更加准确,于是我在测试的时候将最后一行代码的3改成了5。通过测试,在1000和10000中的每个素数的计算时间都是0。10万和100万也都是零。我觉得是因为这本书的历史比较久远了,当时的硬件比不上现在的了。于是我又用了一千万来测试,返回的5个时间分别是0、15、15、15、31,用一亿来测试返回的5个时间分别是15、31、47、62、78,和根号10的差距不是太遥远吧。十亿返回的5个时间分别是47、94、141、297、391。至此这道习题就算做完了,稍有不足都请读者列出。