亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

[LeetCode] Count Primes

Shisui / 2680人閱讀

摘要：用數(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ù)組flag標(biāo)記非質(zhì)數(shù)，每當(dāng)出現(xiàn)一個(gè)flag[i]為false，計(jì)數(shù)器count加一。
關(guān)于質(zhì)數(shù)有三點(diǎn)：

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

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

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

首先，我們用i從3到Math.sqrt(n)進(jìn)行標(biāo)記。
其次，根據(jù)上述的第2、3兩點(diǎn)，通過乘積i*j對應(yīng)index的方法對在flag中對合數(shù)為index的值賦值true，j+=2，外層一樣，i+=2，因?yàn)榇笥?的數(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://www.ezyhdfw.cn/yun/66096.html

相關(guān)文章

  • [Leetcode] Count Primes 數(shù)素?cái)?shù)

    摘要：利用這個(gè)性質(zhì)，我們可以建立一個(gè)素?cái)?shù)數(shù)組，從開始將素?cái)?shù)的倍數(shù)都標(biāo)注為不是素?cái)?shù)。第一輪將等表為非素?cái)?shù)，然后遍歷到，發(fā)現(xiàn)沒有被標(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 評論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

    摘要：建兩個(gè)新數(shù)組，一個(gè)存數(shù)，一個(gè)存。數(shù)組中所有元素初值都是。實(shí)現(xiàn)的過程是，一個(gè)循環(huán)里包含兩個(gè)子循環(huán)。兩個(gè)子循環(huán)的作用分別是，遍歷數(shù)組與相乘找到最小乘積存入再遍歷一次數(shù)組與的乘積，結(jié)果與相同的，就將加，即跳過這個(gè)結(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ù)雜度考慮一個(gè)，的值是下一個(gè)可能的替補(bǔ)值。思路數(shù)組中保存的是之前保留到的值，因?yàn)橄乱粋€(gè)可能的值是和之前的值的倍數(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元查看
<