质数/素数的检验与生成

在做Project Euler的第4题,是关于质数的。

有以下事实很有趣:

1. 一个合数总是可以分解成若干个质数的乘积。很明显,也很容易证明。

2. 判断一个数X是质数,只要用X依次除小于SQRT(X)的质数,看是否可整除即可。如果你有一个生成过的质数序列的缓存,这里就可以用上了...

3. 判断一个数X不是质数,可首先检查它是不是某个质数的整数倍,这里同样可以用上缓存。

4. 纯数值计算,Ruby 1.9比Ruby 1.8至少快一倍

所以:

1. 要分解一个数,我们只需要尝试质数即可,所以我们需要一个从小到大的质数序列

2. 要生成一个质数序列,非常容易,只要保存一个质数由小到大的数组,这个数组中开始可以只有一个数字2,然后:

1) 取出数组中最大的数,作为要寻找的下一个素数X

2) 从已有的质数序列中取出所有小于SQRT(X)的数,用X依次除,只要除不尽,X就是素数,只要除尽,X就不是素数

3) 如果X是素数,将X加入数组

4) 如果X不是素数,将X加1,重复2)

comments powered by Disqus