204. Count Primes，204countprimes

204. Count Primes，204countprimes

Description:

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

 1 int countPrimes(int n) {
 2     bool *isprime = (bool*)malloc(n*sizeof(bool));
 3     int i,j;
 4     int count;
 5     if(n <= 2)
 6         return 0;
 7     if(n == 3)
 8         return 1;
 9     count = n - 2;                      //去掉1不是素數，2是素數，剩下的conut計算素數的個數，就是減去3到n之間的合數
10     for(i = 3; i < n; i++)
11     {
12         if(i % 2)
13             isprime[i] = true;             
14         else{                                //總數去掉2的冪數的數
15             isprime[i] = false;
16             count--;
17         }
18     }
19     for(i = 3; i * i <= n; i++)                    //這裡判斷到n的開方，是因為i到i*i之間所有的數都會被判斷到
20     {
21         if(isprime[i])                       //當i是質(素)數的時候，i的所有的倍數必然是合數
22         {
23             for(j = i*i; j < n; j+=i)
24                 if(isprime[j])                 //j從i*i 開始判斷，因為i *(i-1)已經判斷過了
25                 {
26                     isprime[j] = false;           
27                     count--;                   //總數去掉為合數的數
28                 }
29         }
30     }
31     free(isprime);
32     return count;
33     
34 }