思路为：
1->2是质数，所有是偶数的都是2的倍数一定不是质数（除了2，偶数一定不是质数，因此我们不需要考虑任何偶数）
2.->从3开始考虑到n的奇数，其中某个数，如3的所有整数倍的数都不是质数，我们需要找到不小于n为止，即全部考虑到
->这样的话，当我们遍历到9的时候，因为9不是第一次出现，他已经被3考虑为非质数了。
//代码如下：
public int countPrimes(int n) { int res=0; if(n>2) res++; else return res; boolean[] isPrime=new boolean[n]; isPrime[2]=true; //偶数一定不是质数，因此我遍历所有奇数寻找质数 for(int i=3;i<n;i+=2){ if(!isPrime[i]){//如果是质数 res++; for(int j=3;i*j<n;j+=2){ isPrime[i*j]=true; } } } return res; }
//当我们为3的时候已经把n内所有3的倍数都设置过了，当为5的时候我们就没必要再去设置*3了，当为7的时候就没有必要设置*3和*5的了，由此我们优化为下方代码
每次直接从他的本身为倍数起始即可！
int res=0; if(n>2) res++; else return res; boolean[] isPrime=new boolean[n]; isPrime[2]=true; //偶数一定不是质数，因此我遍历所有奇数寻找质数 for(int i=3;i<n;i+=2){ if(!isPrime[i]){//如果是质数 res++; for(long j=i;i*j<n;j+=2){ isPrime[(int) (i*j)]=true; } } } return res;
原文：https://www.cnblogs.com/ningxinjie/p/13193036.html