筛选法求质数

在这里看到用Lua和Python写的使用筛选法求质数的代码，俺自己也写了写，Python版用到了上面链接中一位兄弟的tips

先来C语言版的:

#include <stdio .h>
#include <math .h>

#define NUM 2000000

int main(void)
{
    int primes[NUM];
    int i,j;
    for (i=0;i<num ;i++) {
        primes[i] = 1;

    }
    primes[0] = 0;
    primes[1] = 0;
    for (i=1;i<(long)sqrt(NUM)+1;i++) {
        if (primes[i]) {
            for (j=pow(i,2);j<NUM;j+=i) {
                primes[j] = 0;
            }
        }
    }

    long sum = 0;
    for (i=0;i<NUM;i++) {
        if (primes[i]) sum+=i;
    }
    printf("%ld\n",sum);

    return 0;
}

计算两百万以内质数和大约0.1秒左右：

[cocobear@cocobear wxpython]$ time ./a.out
142913828922

real	0m0.100s
user	0m0.088s
sys	0m0.012s

接着来可爱的Python版:

from math import sqrt
NUM = 2000000
prime_num = [i for i in xrange(NUM+1)]
for i in xrange(2,int(sqrt(NUM))+1):
    if prime_num[i]:
        start = i**2
        step  = i
        prime_num[start::step] = ( (NUM - start)/step + 1)*[0]
print sum(prime_num)-1

执行时间1秒多点：

[cocobear@cocobear wxpython]$ time python prime.py
142913828922

real	0m1.204s
user	0m1.051s
sys	0m0.093s

Python不到10行的代码也有不错的效率:-)
以上测试平台为:

Fedora 9 AMD64 4600+ 4G

计算5的阶乘

reduce(lambda x,y:x*y,range(1,5+1))