[LeetCode] 204. Count Primes

cheukyin 發(fā)布于2019-08-16 13:38 / 1952人閱讀

Problem

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

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Solution

class Solution {
    public int countPrimes(int n) {
        boolean[] notPrime = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!notPrime[i]) {
                count++;
                for (int j = 2; j*i < n; j++) {
                    notPrime[i*j] = true;
                }
            }
        }
        return count;
    }
}

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

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

相關(guān)文章

204. Count Primes

摘要：題目鏈接思路首先要知道如何判斷一個(gè)數(shù)字是否為素?cái)?shù)。具體方法可以看這里其次，如果樸素的判斷，那么會(huì)因?yàn)樾实紫露瑫r(shí)。所以在我們每次找到素?cái)?shù)的時(shí)候，可以把素?cái)?shù)的倍數(shù)都標(biāo)記為非素?cái)?shù)。這樣可以節(jié)省輪詢的時(shí)間。算法復(fù)雜度時(shí)間空間代碼題目鏈接：Counting Primes 思路：首先要知道如何判斷一個(gè)數(shù)字是否為素?cái)?shù)。具體方法可以看這里其次，如果樸素的判斷，那么會(huì)因?yàn)樾实紫露瑫r(shí)。所以在我...

王笑朝 2019-07-30 16:58 評(píng)論0 收藏0
[Leetcode] Count Primes 數(shù)素?cái)?shù)

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

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

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

alphahans 2019-08-21 16:20 評(píng)論0 收藏0
[LeetCode] Count Primes

摘要：用數(shù)組標(biāo)記非質(zhì)數(shù)，每當(dāng)出現(xiàn)一個(gè)為，計(jì)數(shù)器加一。關(guān)于質(zhì)數(shù)有三點(diǎn)大于的質(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 評(píng)論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號(hào)記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會(huì)根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評(píng)論0 收藏0