国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[Leetcode] Count Primes 數素數

Achilles / 1738人閱讀

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

Count Primes 
Description:


Count the number of prime numbers less than a non-negative number, n.
埃拉托斯特尼篩法 Sieve of Eratosthenes 復雜度

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

思路

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

代碼 
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倍...都標記為非素數
                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;
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64499.html

相關文章

  • 204. Count Primes

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

    王笑朝 評論0 收藏0

  • 線性素數篩選（linear sieve for prime number）

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

    biaoxiaoduan 評論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 評論0 收藏0

  • [LeetCode] Count Primes

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

    Shisui 評論0 收藏0

  • [LintCode/LeetCode] Super Ugly Number

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

    wuyumin 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<