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 }