又是一年到来，感觉光阴虚度，虚长一岁，无所事事。该写些东西了，正好将去年底写的一个基于haskell程序翻译的一种快速的素数筛法，稍为整理下放上来，作为新的一年的开始吧。
该筛法是基于Postponed Filters Siever，效率比较高，haskell代码如下:
primes = 2: 3: sieve (tail primes) [5,7..] where sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0] -- or: filter ((/=0).(`rem`p)) t where (h,t) = span (< p*p) xs
在我的机器上200万以内的时间如下real 0m2.654suser 0m2.385ssys 0m0.037s
我将其翻译为c语言程序，增加了一个求素数和的功能，其使用方法如下：
Usage: qsieve [-j <jobs>] [-l] [-s] <max_range>
-l list all prime numbers in range
-s get sum of prime numbers in range
-j number of qsieve threads
-h show help message
具体代码见如下链接。
http://download.csdn.net/source/3023881
这是一个小的工程打包，使用git作为版本管理工具，有已经编译好的可执行程序，不过是在mac os 10.6的系统上编译的，在linux下应该也可以编译通过。在我的笔记本上的运行时间如下所示：
求200万以内所有素数的和，情况如下：
$ time ./qsieve -j 4 2000000
Max range of prime number is 2000000
Thread number is 4
sieved_num=148933
Sum of 2000000 primes is 142913828922
real 0m0.379s
user 0m0.600s
sys 0m0.013s
求2000万以内所有素数的和，情况如下：
$ time ./qsieve -j 4 20000000
Max range of prime number is 20000000
Thread number is 4
sieved_num=1270607
Sum of 20000000 primes is 12272577818052
real 0m8.173s
user 0m13.941s
sys 0m0.130s
有兴趣的可以在自己的机器上编译一下，看看运行的情况如何。
