Ahri-珊

day14将分享LeetCode算法题204。

204. Count Primes

计算比n小的数当中的质数个数。

心路历程

1.新建一个哈希数组用于存放每一个数是否是质数的判断结果（从2开始，1不是质数）

2.如果这个数没有被判断（hash[i]未被初始化），执行判断

3.判断：这个数的倍数（j）都不是质数，将hash[j]的值初始化

4.遍历哈希数组，未被初始化的元素个数即质数个数

5.为什么（ii<n）不是（i<n）：判断到i时，ii之内的数没被初始化的已经全是质数了

代码：

var countPrimes = function(n) {
    var hash = new Array(n);
    var count = 0;
    for(let i=2;i*i<n;i++)
        {
           if(!hash[i])
            {
               for(let j=i*i;j<n;j+=i)
                   hash[j]=true;
            }
        }
    for(let i=2;i<n;i++)
    {
        if(!hash[i])
            count++;
    }
    return count;
};

END