Description:

Count the number of prime numbers less than a non-negative number, n.

计算小于n的非负整数中素数的个数。
素数又称质数，是指只能被1和它自身相除的自然数。需要注意的是1既不是素数也不是合数。2是最小的素数。

使用判断一个数是否是素数的函数，那么这个函数需要进行一轮循环，在给定的小于n中又要进行一轮循环。所以时间复杂度是O(n^2)。

可以对判断一个数是否是素数的函数进行优化，对于数i，可以只对2到√i之间的数进行判断，这样时间复杂度降低到了O(nlogn)。

但是上面的解法在leetcode中还是超时。

于是想是否存在只进行一轮循环的方法，即在遍历1至n-1一次的过程中记录下素数的个数，但是后面就不知道怎么处理。

然后看leetcode中的小提示,发现了一种更优的寻找素数的方法。首先看下面的这个图：

这个图其实就道出了这个算法是怎么进行的。使用一个长度是n的hash表，最开始这个hash表中的所有元素都是没有被处理的，从2开始遍历，如果这个元素没有被处理，那么将素数的个数加1，然后将2*2,2*3,2*4……2* k（ 2* k < n）标记为已经被处理了的。接着开始处理3，同理将3*2,3*3,3*4…..3*m( 3 * m < n)标记为已被处理了的，接着是4，由于这个元素已经被处理，继续向后遍历，这样一直处理下去。<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPrTT1eK1wMzi1tDT1tLiyra1vcHL0ru49tX7yv274dLns/a74bW81sLOyszitcTQoby8x8mhozwvcD4NCjxwPsG91ta94reot9ax8Mjnz8KjujwvcD4NCjxwcmUgY2xhc3M9"brush:java;"> class Solution { public: /* //解法一：超时 int countPrimes(int n) { int count=0; for(int i=2;i<=n;i++) { if(isPrime(i)) count++; } return count; } bool isPrime(int n) { if(n==1) return false; for(int i=2;i*i<=n;i++) { if(n%i==0) return false; } return true; } */ //解法二： int countPrimes(int n) { int * mask=new int[n]();//可以在这里直接对动态数组进行初始化 int count=0; for(int i=2;i