[LeetCode] Count Primes

Shisui 發布于2019-08-14 15:54 / 2630人閱讀

摘要：用數組標記非質數，每當出現一個為，計數器加一。關于質數有三點大于的質數一定是奇數，如，，奇數中的非質數也一定是奇數的乘積。首先，我們用從到進行標記。標記完所有的合數之后，再用到之間的遍歷，所有未被標記的質數。

Problem

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

Note

用數組flag標記非質數，每當出現一個flag[i]為false，計數器count加一。
關于質數有三點：

大于3的質數一定是奇數，如3，5，7；

奇數中的非質數也一定是奇數的乘積。

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

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

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;
    }
}

常規解法

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;
    }
}

GPU云服務器云服務器 Primes LeetCode LeetCode_String leetcode_35_SearchIn

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

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

[Leetcode] Count Primes 數素數

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

Achilles 2019-08-14 12:28 評論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 2019-08-16 13:38 評論0 收藏0
[LintCode/LeetCode] Super Ugly Number

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

wuyumin 2019-08-14 15:20 評論0 收藏0
Leetcode[313] Super Ugly Number

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

Aklman 2019-08-16 10:27 評論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 2019-08-16 12:37 評論0 收藏0