204. Count Primes

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

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

**思路:**这道题可以考虑用打表的方式来解，但考虑到n值会很大，用数组存储会爆的，所以考虑用指针来保存。

int countPrimes(int n) {
    int *isPrime=(int *)malloc(n*sizeof(int));
    memset(isPrime,0,sizeof(isPrime));
    for(int i=2;i*i<n;i++)
    {
        if(isPrime[i]) continue;
        for(int j=i*i;j<n;j+=i)
        {
            isPrime[j]=1;
        }
    }
    int count=0;
    for(int i=2;i<n;i++)
    {
        if(!isPrime[i]) count++;
    }
    return count;
}