204. 计数质数

难度：简单

题目

统计所有小于非负整数 n 的质数的数量。

示例：

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

Reference

题解

基本思路： 从2开始，在数列\(2, 3, \cdots, n\)中划去所有2的倍数，剩下的第一个没有被划去的数字3即为质数，再花旗所有3的倍数，剩下的第一个没有被划去的数字5即为质数。重复如上操作，直到检查完所有小于等于\(\sqrt n\)的整数，即完成。

数字是否划去的状态可以使用一个数组控制，也可以用一个类型中的1位表示。

代码如下：

int countPrimes(int n)
{
    unsigned char *map = memset(malloc(sizeof(unsigned char) * ((n + 1 >> 3) + 1)), 0x55, sizeof(unsigned char) * ((n + 1 >> 3) + 1));
    int i = 0, j, ret = 0, sq = (int)sqrt(n), increment = 1, start = 2;
    *map = 0x51;
    for (i = 3; i <= sq; i++)
        if (!(map[i >> 3] & (unsigned char)1 << (i & 7)))
            for (j = i * 3; j <= n; j += i << 1)
                map[j >> 3] |= (unsigned char)1 << (j & 7);
    for (i = 2; i < n; i++)
        if (!(map[i >> 3] & (unsigned char)1 << (i & 7)))
            ret++;
    return ret;
}

评论