LeetCode#204 Count Prime

Problem Definition:

　　Count the number of prime numbers less than a non-negative number, n.

Hint:

　　Let's start with a isPrime function. To determine if a number is prime, we need to check if it is not divisible by any number less than n.

　　The runtime complexity of isPrime function would be O(n) and hence counting the total prime numbers up to n would be O(n²). Could we do better?

Solution: (筛选法)

　 1. use square root of n.
     2. use non-prime numbers as the step
     3. use i*i as the start.
     4. use count-- in every loop, avoiding another traversal.

 1 def countPrime(n):
 2     if n<=2:
 3         return 0
 4     if n==3:
 5         return 1
 6     prime=[True]*n
 7     count=n-2
 8     rt=sqrt(n)
 9     for i in range(2,rt+1):
10         if prime[i]==True:
11             for j in xrange(i*i,n,i):
12                 if prime[j]==True:
13                     prime[j]=False
14                     count-=1
15     return count