欧美一区二区三区老妇人-欧美做爰猛烈大尺度电-99久久夜色精品国产亚洲a-亚洲福利视频一区二区

leetcode中如何實現(xiàn)?統(tǒng)計小于非負數(shù)n的素數(shù)個數(shù)

小編給大家分享一下leetcode中如何實現(xiàn)統(tǒng)計小于非負數(shù)n的素數(shù)個數(shù)，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

創(chuàng)新互聯(lián)專注于企業(yè)網(wǎng)絡營銷推廣、網(wǎng)站重做改版、富縣網(wǎng)站定制設計、自適應品牌網(wǎng)站建設、H5響應式網(wǎng)站、商城網(wǎng)站制作、集團公司官網(wǎng)建設、成都外貿(mào)網(wǎng)站建設、高端網(wǎng)站制作、響應式網(wǎng)頁設計等建站業(yè)務，價格優(yōu)惠性價比高，為富縣等各大城市提供網(wǎng)站開發(fā)制作服務。

leetcode 204.

題目要求：

統(tǒng)計小于非負數(shù)n的素數(shù)個數(shù)。

輸入輸出示例：

Input: 100

Output: 25

解題思路：

題目比較簡單，素數(shù)問題也算是各種問題中常見的問題了。首先要明白的一點是，什么是素數(shù)？素數(shù)又稱為質(zhì)數(shù)，指的是在大于1的自然數(shù)中，除了1和它本身外不再有因數(shù)的數(shù)。

最簡單的思路是，嘗試用n去除2到n-1，發(fā)現(xiàn)有整除，可以確認這不是素數(shù)。但是這樣很費勁有沒有？要統(tǒng)計個數(shù)，就要把所有的數(shù)都算一遍。

再考慮一下，n的因數(shù)不可能大于sqrt（n），那么遍歷從n到sqrt（n）就夠了。但是這樣還是很慢，如果n不大還行，如果n很大，運力的消耗將很嚴重。

再對素數(shù)進行分析，從2到n這中間，仍然會存在很多不靠譜的數(shù)字，比如4,6,8等等，他們必然能被2整除，也就是說，凡是2-sqrt（n）的整數(shù)倍的數(shù)字，那肯定不是素數(shù)了。首先把偶數(shù)排掉，就去掉了一半的數(shù)字，以此類推。

所以，建立一個bool類型的數(shù)組，用來標記是素數(shù)或者不是素數(shù)，長度為n+1.并對它進行初始化，0,1設為false，2,3設為true，從4開始，所有偶數(shù)設為false，其他設為true。

然后設置一個i從2到sqrt（n）的循環(huán)，仍然跳過偶數(shù)。接著內(nèi)層循環(huán)對i的倍數(shù)進行標記false，當把sqrt（n）也標記完的時候，整個array就完成了，最后統(tǒng)計一遍true的次數(shù)，就可以得到結(jié)果了。

不過測試之后發(fā)現(xiàn)有個bug，當n很大的時候長度會超出限制，但是我現(xiàn)在想不出更好的方法了，誰能解答一下？歡迎討論。

Java代碼的實現(xiàn)：

public class Solution {

    public int countPrimes(int n) {

        boolean prime[] = new boolean[n+1];

        //initial array 排掉偶數(shù)，注意開頭幾個單元的標注

        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;

        //統(tǒng)計輸出結(jié)果

        for(int i = 1; i < n+1; i++)

            {

                if(prime[i])

                    result++;

            }

            return result;

    }

}

以上是“l(fā)eetcode中如何實現(xiàn)統(tǒng)計小于非負數(shù)n的素數(shù)個數(shù)”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學習更多知識，歡迎關注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

當前題目：leetcode中如何實現(xiàn)?統(tǒng)計小于非負數(shù)n的素數(shù)個數(shù)
網(wǎng)站鏈接：http://chinadenli.net/article36/gepipg.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站收錄、企業(yè)網(wǎng)站制作、用戶體驗、動態(tài)網(wǎng)站、App開發(fā)、服務器托管

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

h5響應式網(wǎng)站建設