题目描述
Count the number of prime numbers less than a non-negative number, n。
本题要求我们求出小于n的数中共有多少个质数。相信大部分同学在刚开始学习C语言的时候估计都写过判断一个数为质数的程序。一般的思路为：
bool isPrime(int num) {int s = sqrt(num) + 1;for( int i = 3; i != s; ++i) {if (num mode i == 0)return false;}return true;}
但是若对小于n的每一个数进行上述计算，会重复很多次，，效率很低。
这里LeetCode给出了两个提示链接：
How Many Primes Are There?Sieve of Eratosthenes
第一个链接给出了本题答案的近似估计公式，第二个介绍了一种很好的算法。这里介绍一下第二种思路，想了解得更全面的同学，请猛戳上面的第二个链接。
根据上述思路处理，直到获得所有的质数为止。
这里还可以进行一个优化，即对于质数 p，排除掉p的整数倍后，剩下的元素中满足 的元素k均为质数。这里简单证明一下：
参考下图可以更容易了解（这里盗一下wiki的图~~）
代码
本题使用动态数组表示小于n的每个元素是否为质数，效率比较高，下面的代码时间为50+ms， 我试过用vector时间一下子到了800+ms，太可怕了。
class Solution {public:int countPrimes(int n) {if (n <= 2) return 0;bool *p = new bool[n];memset(p, true, sizeof(bool) * n);for (int i = 2; i * i < n; i++){if (p[i]){for (int j = 2; j * i < n; j++)p[i * j] = false;}}int cnt = 0;for (int i = 2; i != n; i++)if (p[i]) cnt++;delete[] p;return cnt;}};
我无所事事的度过了今天，是昨天死去的人们所期望的明天。
