成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[LeetCode] Count Primes

Shisui / 2633人閱讀

摘要：用數(shù)組標(biāo)記非質(zhì)數(shù)，每當(dāng)出現(xiàn)一個為，計數(shù)器加一。關(guān)于質(zhì)數(shù)有三點大于的質(zhì)數(shù)一定是奇數(shù)，如，，奇數(shù)中的非質(zhì)數(shù)也一定是奇數(shù)的乘積。首先，我們用從到進行標(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ù)組flag標(biāo)記非質(zhì)數(shù)，每當(dāng)出現(xiàn)一個flag[i]為false，計數(shù)器count加一。
關(guān)于質(zhì)數(shù)有三點：

大于3的質(zhì)數(shù)一定是奇數(shù)，如3，5，7；

奇數(shù)中的非質(zhì)數(shù)也一定是奇數(shù)的乘積。

對于一個很大的數(shù)n，它的兩個因數(shù)i和j中一定有一個小于n的開方，所以我們讓i <= Math.sqrt(n)，j >= n，這樣可以避免重復(fù)討論一些情況。

首先，我們用i從3到Math.sqrt(n)進行標(biāo)記。
其次，根據(jù)上述的第2、3兩點，通過乘積i*j對應(yīng)index的方法對在flag中對合數(shù)為index的值賦值true，j+=2，外層一樣，i+=2，因為大于3的數(shù)中只有奇數(shù)有可能是質(zhì)數(shù)，而這些質(zhì)數(shù)i可以通過j的循環(huán)標(biāo)記所有i作為因數(shù)的合數(shù)。
標(biāo)記完所有的合數(shù)之后，再用Math.sqrt(n)到n之間的遍歷，count所有未被標(biāo)記true的質(zhì)數(shù)。

Solution 
public class Solution {
    public int countPrimes(int n) {
        boolean[] mark = new boolean[n];
        if (n <= 2) return 0;
        int i = 3, count = 1; //i from 3, so there is one prime: 2
        while (i <= Math.sqrt(n)) {
            if (!mark[i]) {
                count++;
                int j = i;
                while (i*j < n) {
                    mark[i*j] = true;
                    j += 2;
                }
            }
            i += 2;
        }
        while (i < n) {
            if (!mark[i]) count++;
            i += 2;
        } 
        return count;
    }
}

常規(guī)解法

class Solution {
    public int countPrimes(int n) {
        if (n <= 2) return 0;
        boolean[] primes = new boolean[n];
        Arrays.fill(primes, true);
        for (int i = 2; i < n; i++) {
            for (int j = i+i; j < n; j += i) {
                primes[j] = false;
            }
        }
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (primes[i]) count++;
        }
        return count;
    }
}

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

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

相關(guān)文章

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

    摘要：利用這個性質(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-nega...

    Achilles 評論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

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

  • Leetcode[313] Super Ugly Number

    摘要：滾動求最大值復(fù)雜度考慮一個，的值是下一個可能的替補值。思路數(shù)組中保存的是之前保留到的值，因為下一個可能的值是和之前的值的倍數(shù)關(guān)系。 Leetcode[313] Super Ugly Number Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whos...

    Aklman 評論0 收藏0

  • [LintCode/LeetCode] Check Sum of K Primes

    Problem Given two numbers n and k. We need to find out if n can be written as sum of k prime numbers. Example Given n = 10, k = 2Return true // 10 = 5 + 5 Given n = 2, k = 2Return false Solution pub...

    lakeside 評論0 收藏0

發(fā)表評論

0條評論

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