用厄拉多塞法筛选素数

最近在看SICP,这本书写的确实不错。3.5节中讲到了无穷流对素数的一个应用:用厄拉多塞筛法来构造出素数的无穷流。这个筛选思路值得记录一下。

厄拉多塞是公元前3世纪希腊亚历山大的哲学家。他由于第一个给出了地球的圆周的精确估计而闻名。他的计算方式是观察夏至日正午影子的角度。虽然厄拉多塞筛法历史如此悠久,但仍成为专用硬件“筛”的基础,直至最近都一直是确定大素数存在的有力工具。直到20世纪70年代,这种算法被概率算法超越。

思路

(前面关于流和无穷流的定义以及说明直接略过了,感兴趣的可以自己看)首先,这个无穷流从整数2开始,因为这是第一个素数。为了得到其余的素数,就需要从2后面的整数中过滤掉所有2的倍数,这样就留下一个从3开始的无穷流,而3也就是下一个素数。现在再从这个流的后面部分过滤掉所有3的倍数,这样就留下一个从5开头的无穷流,而5又是下一个素数,就这样继续下去。换句话说,这种方法就是通过一个筛选过程构造出各个素数。

筛选过程描述如下

对流S做筛选就是形成一个流,其中的第一个元素就是S的第一个元素,得到其随后的元素的方式是从S的其余元素中过滤掉所有S的第一个元素的倍数,而后再对得到的结果进行同样的筛选。

代码

1
2
3
4
5
6
7
8
9
(define (sieve stream)
(cons-stream
(stream-car stream)
(sieve (stream-filter
(lambda (x)
(not (divisible? x (stream-car stream))))
(stream-car stream)))))

(define primes (sieve (integers-starting-from 2)))

上面的Lisp代码写得还是很精练的,没有任何多余的代码。

将素数筛看作一个信号处理系统

我们可以将上面的厄拉多塞筛法看作是一个信号处理系统。出入流溃入“反cons”,分解出这个流的首元素和其余元素,用这个首元素去构造一个可除性过滤取,让该流的其余部分穿过这个过滤器,这个过滤器的输出再溃入到另一个筛块,而后将原来的首元素cons到这个内部筛的输出上,形成最终的输出流。这样,不仅输入流是无穷的,信息处理器也是无穷的。

听了这么多年的播客,终于也做了一回嘉宾

(图片来源:http://teahour.fm)

2017年10月31日,星期二,下午2点,如约接到了国内某容器云公司的电话面试。

电话是从北京打过来的(我是在南京),刚接到电话,我深吸了一口气,安慰自己要放松,之后按下了接通键。

首先,跟面试官简单介绍了一下自己,然后又问我以前做过什么东西没有,我回答道,之前跟着老师做过项目,也和同学接过私活做过。(刚开始的时候,有点紧张,并且还有点害羞😳,语速也有点快)

接着,又让我具体说一下自己参加过的某一个项目,我就开始介绍我去年和同学做的银团的项目,之后,后面的一系列技术相关的问题就开始了

Read More

CSS3中的box-sizing属性

box-sizing属性是css3中新添加的属性,用来替换原来的css盒子模型,box-sizing属性值的不同,元素的高度和宽度的计算方法也不同。

1
2
3
4
/* box-sizing的三个属性值,我们只针对前两个说明 */
box-sizing: content-box;
box-sizing: border-box;
box-sizing: padding-box;

在默认情况下,设置的widthheight属性都是指元素内容(content box)的高度和宽度,如果这个元素设置了borderpadding的话,那么整个元素的高度和宽度就是:

1
2
totalWidth = border-left + padding-left + width + padding-right + border-right
totalHeight = border-top + padding-top + height + padding-bottom + border-bottom

所以,这个在做相应式设计的时候还是比较复杂的,现在,有了box-sizing属性,就可以根据不同的属性值计算元素的高度和宽度。

  • content-box:这是默认情况,根据这个属性值的名字也能大概猜出会是什么情况,整个元素的高度和宽度其实就是上面的两个公式
  • border-box:这种情况下,你设置的widthheight属性值就是针对整个元素,包括了border,padding,和元素内容。

简单的例子

CSS
1
2
3
4
5
6
7
8
9
10
11
12
13
.box {
width: 150px;
height: 150px;
padding: 50px;
border: 5px solid blue;
background-color: orange;
}
.box1 {
box-sizing: content-box;
}
.box2 {
box-sizing: border-box;
}
HTML
1
2
3
4
5
6
<div class="box box1">
content-box
</div>
<div class="box box2">
border-box
</div>

代码中,我们对两个div设置了相同的height、width、border和padding,可是现实效果却完全不同:

demo

我们仔细分析下,两个div不同的地方在于box-sizing属性,第一个是content-box,第二个是border-box,针对第一个div,

第一个div

我们发现,整个元素的高度和宽度是260x260,而元素的内容的高度和宽度是150x150,正好是我们想要的,对于260这个大小是怎么来的,我们不妨计算一下:

1
2
5+50+150+50+5=260  // 高度
5+50+150+50+5=260 // 宽度

正好是260,符合最上面的两个公式,所以最后元素的尺寸是260x260,并不是我们设置的150x150

对于第二个div:

第二个div

很明显可以看到,第二个div里面的内容已经被挤了换行了,这个div的真实的高度和宽度和我们设置的一样,可以它的内容部分的尺寸只有40x40,远小于150,可以看到,这就是content-boxborder-box的区别了,再来计算一下:

1
2
150 = 5+50+40+50+5 // 高度
150 = 5+50+40+50+5 // 宽度

可知,整个元素的高度其实是包括了border、padding和内容的高度,宽度也是如此。

浏览器的兼容性

  • 桌面端

  • 手机端

可以看到,不管是手机端还是桌面端大部分都是不支持padding-box的,所以建议实际开发中避免使用padding-box

跟多详细内容请参考:https://developer.mozilla.org/en-US/docs/Web/CSS/box-sizing


欢迎阅读本篇文章,如有兴趣可以关注博主公众号哦:

博客迁移到Github啦^ _ ^

新的博客,新的起点,新的征程

博客地址先甩上来:https://xydida.com

echo "Welcome to my Blog"

先说明一下,由于博客之前一直是放在OpenShift上面的,不过由于OpenShift最近更新了V3版本,这个版本的更新还挺大的,已经完全是一个容器云服务的平台,但感觉在上面搭一个wordpress比较麻烦,而且受限于国内的网络,之前早就想换到GitHub了,正好趁此机会,尝试一下Hexo,哈哈😄。下图是最新版本的OpenShift的控制台:

openshift manager

由于之前博客上并没有写多少有深度的文章,我也就没有备份,以后将会多输出优质文章,记录生活点滴。