leetcode中如何实现统计小于非负数n的素数个数
小编给大家分享一下leetcode中如何实现统计小于非负数n的素数个数，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！
创新互联专注于企业网络营销推广、网站重做改版、富县网站定制设计、自适应品牌网站建设、H5响应式网站、商城网站制作、集团公司官网建设、成都外贸网站建设、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为富县等各大城市提供网站开发制作服务。
leetcode 204.
题目要求：
统计小于非负数n的素数个数。
输入输出示例：
Input: 100
Output: 25
解题思路：
题目比较简单，素数问题也算是各种问题中常见的问题了。首先要明白的一点是，什么是素数？素数又称为质数，指的是在大于1的自然数中，除了1和它本身外不再有因数的数。
最简单的思路是，尝试用n去除2到n-1，发现有整除，可以确认这不是素数。但是这样很费劲有没有？要统计个数，就要把所有的数都算一遍。
再考虑一下，n的因数不可能大于sqrt（n），那么遍历从n到sqrt（n）就够了。但是这样还是很慢，如果n不大还行，如果n很大，运力的消耗将很严重。
再对素数进行分析，从2到n这中间，仍然会存在很多不靠谱的数字，比如4,6,8等等，他们必然能被2整除，也就是说，凡是2-sqrt（n）的整数倍的数字，那肯定不是素数了。首先把偶数排掉，就去掉了一半的数字，以此类推。
所以，建立一个bool类型的数组，用来标记是素数或者不是素数，长度为n+1.并对它进行初始化，0,1设为false，2,3设为true，从4开始，所有偶数设为false，其他设为true。
然后设置一个i从2到sqrt（n）的循环，仍然跳过偶数。接着内层循环对i的倍数进行标记false，当把sqrt（n）也标记完的时候，整个array就完成了，最后统计一遍true的次数，就可以得到结果了。
不过测试之后发现有个bug，当n很大的时候长度会超出限制，但是我现在想不出更好的方法了，谁能解答一下？欢迎讨论。
Java代码的实现：
public class Solution {
public int countPrimes(int n) {
boolean prime[] = new boolean[n+1];
//initial array 排掉偶数，注意开头几个单元的标注
for(int i = 0; i < n+1; i++)
{
if(i == 0 || i == 1)
prime[i] = false;
else if(i < 4)
prime[i] = true;
else if(i % 2 == 0)
prime[i] = false;
else
prime[i] = true;
}
//标记其他单元
for(int i = 3; i < (int)Math.sqrt(n); i += 2)
for(int j = i + i; j < n + 1; j += i)
{
if(prime[j])
{
prime[j] = false;
}
}
int result = 0;
//统计输出结果
for(int i = 1; i < n+1; i++)
{
if(prime[i])
result++;
}
return result;
}
}
以上是“leetcode中如何实现统计小于非负数n的素数个数”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注创新互联行业资讯频道！
网站栏目：leetcode中如何实现统计小于非负数n的素数个数
分享URL：http://ybzwz.com/article/gepipg.html
