【SICP练习】16 练习1.22



练习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。至此这道习题就算做完了,稍有不足都请读者列出。

时间: 2024-10-05 01:18:03

【SICP练习】16 练习1.22的相关文章

汇编-mov di,16h 和mov di,16有什么不同吗?代码中有注释哪里有问题

问题描述 mov di,16h 和mov di,16有什么不同吗?代码中有注释哪里有问题 DATA SEGMENT STRG DB 30H,31H,32H,33H,34H,35H,36H,37H,38H,39H DB 41H,42H,43H,44H,45H,46H DB 30H,31H,32H,33H,34H,35H,36H,37H,38H,39H DB 41H,42H,43H,44H,45H,46H DATA ENDS CODE SEGMENT ASSUME CS:CODE,DS:DATA S

《Cisco BGP-4 命令与配置手册》——1-6 aggregate-address address mask summary-only

1-6 aggregate-address address mask summary-only Cisco BGP-4 命令与配置手册 语法描述: address:聚合路由的IP地址. mask:聚合路由的掩码. 用途:在BGP表中创建聚合路由表项.只有当BGP表中存在待创建聚合路由的明细路由时,才能创建出相应的聚合路由.这种形式的aggregate-address命令会在抑制所有明细路由的同时,通告聚合路由. Cisco IOS软件版本:10.0 配置案例:抑制明细路由的同时,通告聚合路由 如

双色球073期开奖:冷蓝14开出头奖16注500万

本期号码简析:红球龙头码09.凤尾27.重复号无.相连号16/17/18(三连星).奇偶比3:3.大小比4:2(以17为界).极距18.和值109.蓝球14为大偶数号码(大冷蓝14在遗漏66期后终于开出).[双色球图表] 中彩中心紧急从调节资金中拨出104万弥补当期派彩奖金不足,目前奖池累计金额为1亿6千7百多万元. 一.本期全国投注总额208,376,662元. 二.中奖号码: 红色球号码:09 16 17 18 22 27 蓝色球号码:14 三.中奖结果: 奖级全国中奖注数 每注奖金(元)

22人2天网购火车票一无所获

温州民企员工向http://www.aliyun.com/zixun/aggregation/35558.html">上海铁路局.温州火车站申请公开票源及销售情况 连续2天组织22名员工网络抢购24张春运火车票,结果没买到一张温州一家民企部门经理柳松涛纳闷,"票去了哪里?" 日前,柳松涛分别向上海铁路局.温州火车站快递了信息公开申请表,希望获知想购买的列车班次的票源.销售情况.据快递查询,2份申请表已于21日.19日送达,但到昨天,2家单位均未回复. 几十秒钟余票为零

PHP7 学习笔记(一)Ubuntu 16.04 编译安装Nginx-1.10.3、 PHP7.0.9、Redis3.0 扩展、Phalcon3.1 扩展、Swoole1.9.8 扩展、ssh2扩展(全程编译安装)

 ==================== PHP 7.0 编译安装================== wget http://cn2.php.net/get/php-7.0.9.tar.bz2/from/this/mirror -- 下载php镜像tar xvf mirror -- 解压镜像cd php-7.0.9/ -- 进入安装目录sudo apt-get update -- 更新阿里云库 sudo apt-get install libkrb5-dev \ libc-client200

简单文本编辑器

v一.前言 聚天地之灵气,集日月之精华!一个简单的java文本编辑器由此而生.毕设所需,很是无奈! v二.界面预览      v三.实现思路 v 1.字体选择器的实现 (1).字体类 class MyFont{ private Font font; private Color color; public Font getFont() { return font; } public void setFont(Font font) { this.font = font; } public Color

使用 ssh -R 建立反向/远程TCP端口转发代理

ssh是一个非常棒的工具, 不但能建立动态转发, 例如chrome的Switchy插件用到的就是这个技术. http://blog.163.com/digoal@126/blog/static/163877040201141821810103/ 还能建立TCP的转发隧道, 例如我以前写过的关于使用ssh 隧道加密和加速WAN传输的几个例子. http://blog.163.com/digoal@126/blog/static/163877040201342383123592/ http://bl

[转贴]改好DEBUG七处缺点的comexe实现报告

 改好DEBUG七处缺点的comexe实现报告   首先声明,本文所指DEBUG,系DOS 6.22,win 98及2k三者DEBUG.EXE. (1) DEBUG命令T及P的2处缺点 跟踪命令T,建立在8086标志寄存器第8位(自陷位)置1后,处理器执行完一条 被跟踪指令,就进单步中断1的基础上(进入时,被调试进程栈顶3个字,被无辜破坏). DEBUG预先接管中断1,在那里,对被跟踪指令的执行完现场,先保存,后显示. 于是,DEBUG用以下5步,让欲跟踪的指令,在自陷位持有1的处理器环境下,间

memory prefetch浅析

最近在用vtune分析程序性能瓶颈时发现一些内存访问的地方竟然成了cpu热点.经过仔细分析,发现这些热点主要是对大数组非连续位置的访问的引起的,比较消耗cpu的原因应该是cache不命中.因为像这样局部性很差的内存访问逻辑,对cache是很不友好的.于是想到了prefetch-- x86(以及其他很多体系结构的CPU)提供了prefetch系列指令,用于将指定地址的内存预取到cache.如:"prefetcht0 (%rax)",将以$rax所保存的值为地址的内存所在的cache li