Count Primes

【问题描述】

Description:

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

【解决方案】

Wiki：

int countPrimes(int n)
{
    if(n < 0)
    {
        return -1;
    }

    int i,j;
    int count = 0;
    char *primes = (char *)malloc(sizeof(char) * n);

    memset(primes, 0, sizeof(char) * n);

    primes[0] = 1;
    primes[1] = 1;

    for(i = 2; i * i < n; i++)
    {
        if(!primes[i])
        {
            for(j = i; j * i < n; j++)
            {
                primes[i * j] = 1;
            }
        }
    }

    for(i = 2; i < n; i++)
    {
        if(!primes[i])
        {
            count++;
        }
    }

    free(primes);
    primes = NULL;

    return count;
}