leetcode刷题记录-204. Count Primes

1.题目要求

　　Description:
　　Count the number of prime numbers less than a non-negative number, n.
　　就是给定一个非负整数ｎ，找出小于n的质数的个数

---

2.问题分析

　　质数（也叫素数）的定义：大于等于2，且只能被1和自己整除

---

3.解题思路

• 思路一
  　　对于范围【1,n)的每个数，依次从1开始遍历，统计整除的次数，如果次数为2，说明是质数，从而统计出来小于n的质数的个数。
  　　代码如下：

int countPrimes(int n)
{
    int i, cnt, output = 0;
    while (n >= 2)
    {
        n--;
        cnt = 0;
        for (i = 1; i <= n; i++)
        {
            if (n%i == 0)
                cnt++;
        }
        if (cnt == 2)
            output++;

    }
    return output;
}

　　提交的时候报错，时间复杂度太高，输入的n越大，那么耗时越长。。。所以不可取。在此基础上稍微改进，见思路二

• 思路二
  　　查找有关判断一个数是否为质数的方法，看到篇博客，写的很好
  　　https://blog.csdn.net/huang_miao_xin/article/details/51331710，里面提到了要判断一个数是否为质数，其实并不需要从1判断到n，因为一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)。所以只需要遍历到sqrt(n)即可，
  　　实现代码如下：

int countPrimes(int n)
{
    int i, cnt=0, output = 0;
    int n_sqrt;
    if (n == 2)
        output = -1;
    while (n >= 2)
    {
        n--;
        n_sqrt = sqrt(n)+1;
        cnt = 0;
        for (i = 2; i <= n_sqrt; i++)
        {
            if (n%i == 0)
                cnt++;
        }
        if (cnt == 0)
            output++;
    }
    return output;
}

　　这种方法的效率仍然比较低，上面的博客里面还提到了第三种方法也很巧妙，这里不详述。

---

• 思路三
  　　上面两个代码都不通过。。。心很累。于是向讨论区大神求助，果然找到了好的方法，先贴代码：
  　　

int countPrimes(int n)
{
    vector<bool> prime(n, true);
    prime[0] = prime[1] = false;
    int i,j;
    for (i = 0; i < sqrt(n); i++)
    {
        if (prime[i])
        {
            for (j = i*i; j < n; j += i)
                prime[j] = false;
        }
    }
    return count(prime.begin(), prime.end(),true);
}

　　乍一看确实不怎么好懂，可以参考*上的解释，讲的很详细，链接在这里：https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes，示意图如下:

　　这种思路就是用这种方法实现的，时间复杂度也很低。需要注意的是j一定不能从i开始（不然就会把i自身给排除掉），然后每次递增i，这样就会把所有不是质数的数字都遍历到，剩下的就全是质数啦！
　　注：如果严格按照*上的来的话，for循环里面应该是
　　(j=2*i;j<n;j+=i),改成从i*i开始则进一步减小了时间复杂度,而且效果是一样的.