输入：n = 10输出：4

输入：n = 1输出：0

题目分析：

本题用埃氏筛法（素数筛）可以十分简便的解出这道题，其原理为从 1 到 n 遍历，假设当前遍历到 m，则把所有小于 n 的、且是 m 的倍数的整数标为和数；遍历完成后，没有被标为和数的数字即为质数。

代码：

int countPrimes(int n){	if(n<=2)	return 0;	vector
    
     prime(n,true);	int count=n-2;//去掉不是质数的1	for(int i=2;i<=n;++i)	{	   if(prime[i])	   for(int j=2*i;j
    

优化： 利用素数的一些特性可以对代码进行优化

int countPrimes(int n){	if(n<=2)	return 0;	vector
    
     prime(n,true);    int i=3,sqrtn=sqrt(n),count=n/2;//偶数一定不是质数	while(i<=sqrtn)//最小质因子一定小于等于开方数 	{	   for(int j=i*i;j