前言說明

算法學(xué)習(xí)，日常刷題記錄。

題目連接

計數(shù)質(zhì)數(shù)

題目內(nèi)容

統(tǒng)計所有小于非負(fù)整數(shù)n的質(zhì)數(shù)的數(shù)量。

示例1:

輸入：n = 10

輸出：4

解釋：小于10的質(zhì)數(shù)一共有4個, 它們是2, 3, 5, 7。

示例2:

輸入：n = 0

輸出：0

示例3:

輸入：n = 1

輸出：0

提示：

0 <= n <= 5 * 10^6

分析過程

按照傳統(tǒng)的方法，通過從2開始遍歷到n - 1，逐個判斷是否為質(zhì)數(shù)，統(tǒng)計數(shù)量。

因為從3開始，質(zhì)數(shù)肯定是奇數(shù)，所以遍歷時每次自增2，減少遍歷的次數(shù)。

而判斷每一個數(shù)是否為質(zhì)數(shù)時，也只需要遍歷到這個數(shù)的平方根即可，因為一個數(shù)的因數(shù)不可能大于它的平方根。

所以代碼如下：

class Solution {
    public int countPrimes(int n) {
        if (n < 3) {
            // 若n小于3，統(tǒng)計的是小于2的質(zhì)數(shù)，因為沒有小于2的質(zhì)數(shù)，所以結(jié)果為0
            return 0;
        } else {
            // 質(zhì)數(shù)數(shù)量，初始數(shù)量為1，因為2是質(zhì)數(shù)，后面的for循環(huán)從3開始循環(huán)了
            int num = 1;

            // 從3開始循環(huán)判斷，每次自增2，因為偶數(shù)不是質(zhì)數(shù)，不用判斷
            for (int i = 3; i < n; i += 2) {
                // 是否為質(zhì)數(shù)
                boolean isPrime = true;

                // 從3循環(huán)到這個數(shù)的平方根
                for (int j = 3; j * j <= i; j += 2) {
                    if (i % j == 0) {
                        // 若能被除盡，則不是質(zhì)數(shù)
                        isPrime = false;
                        break;
                    }
                }

                if (isPrime) {
                    // 質(zhì)數(shù)數(shù)量加1
                    ++num;
                }
            }

            return num;
        }
    }
}

但是提交結(jié)果顯示運行超時。

運行結(jié)果

我們考慮用埃氏篩算法，如果x是質(zhì)數(shù)，那么2x，3x…一定不是質(zhì)數(shù)。

因此我們可以反過來判斷，判斷合數(shù)，剩下的就是質(zhì)數(shù)。

我們可以用一個布爾數(shù)組來保存n之前的數(shù)，標(biāo)記每一個數(shù)是質(zhì)數(shù)還是合數(shù)。

如果找到了一個質(zhì)數(shù)，那么質(zhì)數(shù)從2倍開始遍歷到n倍，直到小于n，因為x是質(zhì)數(shù)，那么x的倍數(shù)一定不是質(zhì)數(shù)，所以遍歷到的都是合數(shù)，全部標(biāo)記為true。

那有沒有可能出現(xiàn)，一個合數(shù)被標(biāo)記為質(zhì)數(shù)，即false呢？

我們可以設(shè)想，假如有一個合數(shù)被標(biāo)記為false了，那么合數(shù)肯定是等于它之前的某個質(zhì)數(shù)的整數(shù)倍的，但是我們在之前就已經(jīng)把所有的質(zhì)數(shù)的整數(shù)倍判斷過一次了，所以如果是合數(shù)，肯定會被標(biāo)記起來，標(biāo)為true。

所以，不會出現(xiàn)一個合數(shù)被標(biāo)記為質(zhì)數(shù)。

解答代碼

所以需要用空間換時間，使用埃氏篩算法，解答代碼如下：

class Solution {
    public int countPrimes(int n) {
        // 使用埃氏篩算法

        // 定義質(zhì)數(shù)數(shù)量
        int count = 0;

        // 定義布爾數(shù)組，保存n之前每個數(shù)是否為質(zhì)數(shù)，false表示質(zhì)數(shù)，true表示合數(shù)
        boolean[] flag = new boolean[n];

        // 從2開始遍歷到n-1
        for (int i = 2; i < n; i++) {
            if (!flag[i]) {
                // 若i為0，找到質(zhì)數(shù)，質(zhì)數(shù)數(shù)量加1
                ++count;

                // 質(zhì)數(shù)從2倍開始遍歷到n倍，直到小于n，如果x是質(zhì)數(shù)，那么2x，3x…一定不是質(zhì)數(shù)，所以遍歷到的都是合數(shù)，全部標(biāo)記為true
                for (int j = i + i; j < n; j += i) {
                    flag[j] = true;
                }
            }
        }

        // 這里省去了對每一個數(shù)從2開始逐個判斷是否整除來判斷質(zhì)數(shù)，直接標(biāo)記合數(shù)，剩下的就是質(zhì)數(shù)
        return count;
    }
}

提交結(jié)果

執(zhí)行用時51ms，時間擊敗59.83%的用戶，內(nèi)存消耗41.7MB，空間擊敗65.44%的用戶。

運行結(jié)果

原文鏈接

原文鏈接：計數(shù)質(zhì)數(shù)