本文共 1557 字，大约阅读时间需要 5 分钟。

继续新的一天，懒人几天才做一道题，哎，没办法，太懒了加上还有其他的事。

这道题特么的又超时了------TLE-----

题目描述：Count the number of prime numbers less than a non-negative number, n.

---------------------------------------------------------------------------------------------------------------------------------

python

先贴出自己第一次实现的代码

def countprime(n):    count = 0    for j in range(2, n):        # is_prime = Isprime(j)        is_prime = True        for i in range(2, j):            item = j / float(i)            if item == int(item):                is_prime = False        if is_prime:            count += 1        else:            continue    return count

因为一直超时，百度找了个厄拉多塞筛法。

他的思想简单来说，就是划去法，先划去2-N这些数放入表中，然后在2的上面画一个圆圈，然后划去2的其他倍数；第一个既未画圈又没有被划去的数是3，将它画圈，再划去3的其他倍数；现在既未画圈又没有被划去的第一个数 是5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于N的各数都画了圈或划去为止。这时，表中画了圈的以及未划去的那些数正好就是小于 N的素数。

class Solution(object):    def countPrimes(self, n):        """        :type n: int        :rtype: int        -- 厄拉多塞筛法 --        """        is_del = [True, True, False]  # 标记是否划去,0,1是false，2是true        for i in range(3, n):            if i % 2 == 0:                is_del.insert(i, True)  # 划去2的倍数            else:                is_del.insert(i, False)        for i in range(3, n):            if is_del[i] == False:  # 第一次未被划去                if i*i <= n:  # 素数的平方小于等于N                    j = 2                    while j*i < n:                        is_del[j*i] = True                        j += 1        count = 0        for i in range(2, n):            if is_del[i] == False:                count += 1        return count

思想很巧妙，反过来推。

转载地址：http://shyii.baihongyu.com/