[leetcode]204. Count Primes

 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

 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)