<abbr id="4k4cy"></abbr>

<fieldset id="4k4cy"></fieldset>

204. Count Primes

王笑朝發(fā)布于2019-07-30 16:58 / 2753人閱讀

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

題目鏈接：Counting Primes

思路：
首先要知道如何判斷一個數(shù)字是否為素數(shù)。具體方法可以看這里

其次，如果樸素的判斷，那么會因為效率底下而超時。
所以在我們每次找到素數(shù)的時候，可以把素數(shù)的倍數(shù)都標記為非素數(shù)。這樣可以節(jié)省輪詢的時間。

算法復雜度：

時間：O(nloglogn) (time complexity for Sieve of Eratosthenes Algorithm)
空間：O(n)

代碼：

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 3:
            return 0
        primes = [True] * n
        primes[0] = primes[1] = False
        for i in range(2, int(n**0.5)+1):
            if primes[i]:
                for j in range(i*i, n, i):
                    primes[j] = False
        
        return sum(primes)

云服務器 GPU云服務器 Primes Model 204 Count hbase count 命令

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

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

[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ù)素數(shù)

摘要：利用這個性質(zhì)，我們可以建立一個素數(shù)數(shù)組，從開始將素數(shù)的倍數(shù)都標注為不是素數(shù)。第一輪將等表為非素數(shù)，然后遍歷到，發(fā)現(xiàn)沒有被標記為非素數(shù)，則將等標記為非素數(shù)，一直到為止，再數(shù)一遍素數(shù)數(shù)組中有多少素數(shù)。代碼將的倍倍倍都標記為非素數(shù) Count Primes Description: Count the number of prime numbers less than a non-nega...

Achilles 2019-08-14 12:28 評論0 收藏0
leetcode部分題目答案之JavaScript版

摘要：自己沒事刷的一些的題目，若有更好的解法，希望能夠一起探討項目地址自己沒事刷的一些LeetCode的題目，若有更好的解法，希望能夠一起探討 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

alphahans 2019-08-21 16:20 評論0 收藏0
[LeetCode] Count Primes

摘要：用數(shù)組標記非質(zhì)數(shù)，每當出現(xiàn)一個為，計數(shù)器加一。關于質(zhì)數(shù)有三點大于的質(zhì)數(shù)一定是奇數(shù)，如，，奇數(shù)中的非質(zhì)數(shù)也一定是奇數(shù)的乘積。首先，我們用從到進行標記。標記完所有的合數(shù)之后，再用到之間的遍歷，所有未被標記的質(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
線性素數(shù)篩選（linear sieve for prime number）

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

biaoxiaoduan 2019-07-24 18:07 評論0 收藏0