问题描述：
Description:
Count the number of prime numbers less than a non-negative number, n.
思路：
首先我想到的思路是暴力遍历检测，然后计数，所以写了一个判断是否为质数的函数ifPrime，然后遍历所有小于n的奇数判断是否质数并计数。而ifPrime函数判断某数k是否质数的实现，是用小于k^1/2的所有奇数去除k，若存在能整除就不是质数。如代码一。
但是提交后不意外地Time Limit Exceeded了。于是找了下判断质数的方法，找到一个比较符合计数过程并且稍为简单的埃拉托斯特尼筛法Sieve of Eratosthenes。该算法思想是，建立一个很大的数组，然后没找到一个质数，就把该质数的倍数都删除（标记不可能为质数），然后下一次遍历到第一个可能为质数的数字就是质数。实现如代码二。
代码：
代码一：
class Solution {
public:int countPrimes(int n) {if (0 == n || n == 1) return 0;if (n == 2) return 1;if (n == 3) return 2;int count = 1;for (int i = 3; i < n; i+=2){if (isPrime(i)) count++;}return count;}//determine if it is primebool isPrime(int n){if (1 == n) return false;if (2 == n || 3 == n || 5 == n) return true;if (n % 2 == 0) return false;for (int i = 3; i <= sqrt(n); i+=2){if (n % i == 0) return false;}return true;}
};代码二：
class Solution {
public:int countPrimes(int n) {if (0 == n || 1 == n) return 0;bool *p = new bool[n];for (int i = 2; i < n; i++){p[i] = false;}int count = 0;int last_prime = 1; while (1){for (int i = last_prime + 1; i < n; i++) //遍历前一个质数后的数{if (p[i] == false) //找到第一个，就是新质数{count++;last_prime = i;//将i倍数都置为非质数for (; i < n; i += last_prime){p[i] = true;}break;}//for循环遍历到租后一个下标也没有也没进入"p[i] == false"的条件语句，就说明遍历完毕均为trueif (i == n - 1) return count; }//上一个prime number是n-1时，无法进入for循环，需要这里判断一下并returnif (last_prime == n - 1) return count;}}
};实际上还有不少有趣、有难度的基于概率的算法，更有效。