[Leetcode] Count Primes 數(shù)素數(shù)

Achilles 發(fā)布于2019-08-14 12:28 / 1743人閱讀

摘要：利用這個性質(zhì)，我們可以建立一個素數(shù)數(shù)組，從開始將素數(shù)的倍數(shù)都標(biāo)注為不是素數(shù)。第一輪將等表為非素數(shù)，然后遍歷到，發(fā)現(xiàn)沒有被標(biāo)記為非素數(shù)，則將等標(biāo)記為非素數(shù)，一直到為止，再數(shù)一遍素數(shù)數(shù)組中有多少素數(shù)。代碼將的倍倍倍都標(biāo)記為非素數(shù)

Count Primes

Description:

Count the number of prime numbers less than a non-negative number, n.

埃拉托斯特尼篩法 Sieve of Eratosthenes 復(fù)雜度

時間 O(NloglogN) 空間 O(N)

思路

如果一個數(shù)是另一個數(shù)的倍數(shù)，那這個數(shù)肯定不是素數(shù)。利用這個性質(zhì)，我們可以建立一個素數(shù)數(shù)組，從2開始將素數(shù)的倍數(shù)都標(biāo)注為不是素數(shù)。第一輪將4、6、8等表為非素數(shù)，然后遍歷到3，發(fā)現(xiàn)3沒有被標(biāo)記為非素數(shù)，則將6、9、12等標(biāo)記為非素數(shù)，一直到N為止，再數(shù)一遍素數(shù)數(shù)組中有多少素數(shù)。

代碼

public class Solution {
    public int countPrimes(int n) {
        boolean[] prime = new boolean[n];
        Arrays.fill(prime, true);
        for(int i = 2; i < n; i++){
            if(prime[i]){
                // 將i的2倍、3倍、4倍...都標(biāo)記為非素數(shù)
                for(int j = i * 2; j < n; j =  j + i){
                    prime[j] = false;
                }
            }
        }
        int count = 0;
        for(int i = 2; i < n; i++){
            if(prime[i]) count++;
        }
        return count;
    }
}

云服務(wù)器 GPU云服務(wù)器 Primes LeetCode LeetCode_String leetcode_35_SearchIn

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64499.html

相關(guān)文章

204. Count Primes

摘要：題目鏈接思路首先要知道如何判斷一個數(shù)字是否為素數(shù)。具體方法可以看這里其次，如果樸素的判斷，那么會因為效率底下而超時。所以在我們每次找到素數(shù)的時候，可以把素數(shù)的倍數(shù)都標(biāo)記為非素數(shù)。這樣可以節(jié)省輪詢的時間。算法復(fù)雜度時間空間代碼題目鏈接：Counting Primes 思路：首先要知道如何判斷一個數(shù)字是否為素數(shù)。具體方法可以看這里其次，如果樸素的判斷，那么會因為效率底下而超時。所以在我...

王笑朝 2019-07-30 16:58 評論0 收藏0
線性素數(shù)篩選（linear sieve for prime number）

摘要：轉(zhuǎn)載到其他平臺前也請通知我。算法分析由于我們每次尋找的素數(shù)時，都從開始，逐漸上除，最后到為止，確認(rèn)是否是素數(shù)。接著繼續(xù)排除其有關(guān)合數(shù)。在速度上有略微提升，但是它的算法是主動忽略的相關(guān)合數(shù)，實際意義并不是很大。偶然發(fā)現(xiàn)了這個和stackoverflow很像的地方。打算寫些專欄，一方面，記錄自己學(xué)到的東西。另一方面，也把這些分享給大家。無論是內(nèi)容錯誤還是解釋方式不好，都?xì)g迎各位拍磚。轉(zhuǎn)載...

biaoxiaoduan 2019-07-24 18:07 評論0 收藏0
[LeetCode] 204. Count Primes

Problem Count the number of prime numbers less than a non-negative number, n. Example: Input: 10Output: 4Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7. Solution class Solut...

cheukyin 2019-08-16 13:38 評論0 收藏0
[LeetCode] Count Primes

摘要：用數(shù)組標(biāo)記非質(zhì)數(shù)，每當(dāng)出現(xiàn)一個為，計數(shù)器加一。關(guān)于質(zhì)數(shù)有三點大于的質(zhì)數(shù)一定是奇數(shù)，如，，奇數(shù)中的非質(zhì)數(shù)也一定是奇數(shù)的乘積。首先，我們用從到進(jìn)行標(biāo)記。標(biāo)記完所有的合數(shù)之后，再用到之間的遍歷，所有未被標(biāo)記的質(zhì)數(shù)。 Problem Count the number of prime numbers less than a non-negative number, n. Note 用數(shù)組fla...

Shisui 2019-08-14 15:54 評論0 收藏0
[LintCode/LeetCode] Super Ugly Number

摘要：建兩個新數(shù)組，一個存數(shù)，一個存。數(shù)組中所有元素初值都是。實現(xiàn)的過程是，一個循環(huán)里包含兩個子循環(huán)。兩個子循環(huán)的作用分別是，遍歷數(shù)組與相乘找到最小乘積存入再遍歷一次數(shù)組與的乘積，結(jié)果與相同的，就將加，即跳過這個結(jié)果相同結(jié)果只存一次。 Problem Write a program to find the nth super ugly number. Super ugly numbers a...

wuyumin 2019-08-14 15:20 評論0 收藏0