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://pwwzsj.com/article/gepipg.html