题目大意：
计数质数
统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10 输出: 4 解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=204
解题思路分析：
本题暴力解法是从2循环到n，查看每一个数是否是质数，如果是，返回结果加一。而判断是否为质数，我们只能查看其是否能被2到n-1中的某个数整除，这样一来二层循环的计算压力会非常大，因此我们可以考虑采用排除法。
首先建立一个bool型数组，长度为n，查看哪些数字不是质数。我们从2开始循环，2本身是一个最小的质数，因此，所有2的倍数一定不是质数，因此，我们可以将2的倍数都排除掉，即在bool数组中，将下标为2的倍数位均设为true。之后看数字3，此时如何判定3是否为质数呢？我们知道3如果是合数（不是质数），那么他一定是某个质数相乘得到的，而小于它的质数只有2，并且我们已经排除掉了2的所有倍数，因此我们只要判断bool型数组中index为3的位置是否为true即可，如果是true，说明3是合数，反之如果是false，说明3是质数。当3是质数时，再将3的所有倍数排除掉，以此类推，直到n，我们就能排除掉所有的非质数。这时，只要统计一下bool数组中质数的数量（为false的位）即可。
另外这里有一处可以优化的地方，其实我们不用从2遍历到n，遍历到根号n即可，因为大于根号n的数字如果是非质数，它肯定是包含在小于根号n质数的倍数里。
实现代码：
public int countPrimes(int n) {
// 排除法统计非质数
boolean[] isNotPrime = new boolean[n];
for(int i=2;i*i<n;i++){
if(isNotPrime[i]) continue;
for(int j=2*i;j<n;j+=i){
isNotPrime[j]=true;
}
}
int res=0;
for(int i=2;i<n;i++){
if(!isNotPrime[i]) res++;
}
return res;
}本题解法执行时间为11ms。
Runtime: 11 ms, faster than 74.00% of Java online submissions for Count Primes.
Memory Usage: 39 MB, less than 5.66% of Java online submissions for Count Primes.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-204-count-primes-解题思路分析/