由一个同事发起的编程比赛开始

编程题目：

1、计算1000万、1亿内素数个数?

我的第一个算法：

def isprime(n):
    """Return true if n is prime and False otherwise"""
    if not isinstance(n, int):
        raise TypeError("argument passed to is_prime is not of int type")
    if n < 2:
        return False
    if n == 2:
        return True
    max = int(math.ceil(math.sqrt(n)))
    i = 2
    while i <= max:
        if n%i == 0:
            return False
        i += 1
    return True

def sum_primes(n):
    return len([x for x in xrange(2, n) if isprime(x)]

在数量比较小的时候这个算法还能跑跑，但是如果是亿级的时候要循环这么多次去除显然有点过慢。就一个数这么慢那要算一个区间的数据就更慢。所以需要对算法进行调优。

介绍：拉宾米勒测试算法