Count Primes

这道题照着Hint的思路做就好了，主要是边界问题太恶心

class Solution(object):
    def countPrimes(self, n):
        nums = range(n)
        for i in xrange(2, int(n ** 0.5) + 1):
            if not nums[i]:
                continue
            cur = nums[i] * nums[i]
            while cur < n:
                nums[cur] = 0
                cur += nums[i]

        return sum([1 for x in nums if x != 0]) - 1 if n >= 2 else 0

一个相对更加干净的版本

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        array = [0] * n
        for i in xrange(2, int(n ** .5) + 1):
            if array[i] != 1:
                for j in xrange(i ** 2, n, i):
                    array[j] = 1


        return n - sum(array) - 2 if n >= 2 else 0