您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
小编给大家分享一下leetcode中如何实现统计小于非负数n的素数个数，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！
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的素数个数”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注亿速云行业资讯频道！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。