[leetcode]204. Count Primes

统计小于n的素数的个数

如果判断每一个数是不是素数的话，时间会超时，如下

 1 class Solution(object):
 2     def countPrimes(self, n):
 3         """
 4         :type n: int
 5         :rtype: int
 6         """
 7         c = 0
 8         for i in range(2,n):
 9             if self.isprime(i):
10                 c += 1
11         return c
12     
13     def isprime(self,n):
14         n = int(n**0.5)+1
15         for i in range(2,n):
16             if not n%i:
17                 break
18         else:
19             return True
20         return False

题意要统计素数的个数，那么可以换一种思路，每发现一个素数i，那么i^2，i^2+i...都肯定不是素数

 1 class Solution(object):
 2     def countPrimes(self, n):
 3         """
 4         :type n: int
 5         :rtype: int
 6         """
 7         if n<3:
 8             return 0
 9         flag = [True]*n
10         flag[0],flag[1] = False,False
11         for i in range(2,int(n**0.5+1)):
12             if flag[i]:
13                 flag[i*i:n:i] = [False]*len(flag[i*i:n:i])
14         return sum(flag)