204. Count Primes

Leetcode 問題: 204. Count Primes
Categories:
Tags:

題目

Given an integer n, return the number of prime numbers that are strictly less than n.

傳入一個整數 n，回傳小於整數 n 的所有質數數量

Example

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

Input: n = 0
Output: 0

Input: n = 1
Output: 0

演算法

1. 傳入數字小於 3，則沒有任何質數

假如傳入的數字是小於 3，所以可能是 1 或 2，但找不到小於 1 或 2 的質數，所以直接回傳 0

2. 建立質數對應表，預設是質數

建立一個陣列大小為傳入數字 n 的陣列，並將預設資料都填寫為 1，預設都是質數

索引從 0 開始到 n-1，代表是數字，而數值代表是否為質數

1: 質數，0: 不是質數

因為自己本身數字 n 不用檢查，所以只需要使用 n 個陣列去對應，如果還需要檢查自己 n 是不是質數，鑿需要準備 n+1 個陣列去對應

將索引 0 與 1 設定為不是質數

3. 檢查數字是不是質數

因為預設是質數，所以數字還沒被檢查到，代表該數字是質數

4. 設定質數倍數的所有數字都不是質數

根據 埃拉托斯特尼篩法，質數的所有倍數數字都不是質數，所以當一檢查到質數，可以將這個質數後方的所有倍數數字設定為不是質數

質數 x 倍數 不是值數數值
2 x 2 4
2 x 3 6
2 x 4 8
2 x 5 10
質數 x 倍數 不是值數數值
3 x 2 6
3 x 3 9
3 x 4 12
3 x 5 15

這樣檢查到最後一個數字，就可以找出所有質數了

答案

JavaScript

function countPrimes(checkCountPrimesNumber) {
    if (checkCountPrimesNumber < 3) {
        // 假如傳入的數字是小於 3，所以可能是 1 或 2，但找不到小於 1 或 2 的質數，所以直接回傳 0
        return 0;
    }
    // 整數質數對應表，預設都是質數(1: 質數，0: 不是質數)
    var numberPrimesMapping = new Array(checkCountPrimesNumber).fill(1);
    // 將質數對應的索引 0，數字 0 設定為不是質數
    numberPrimesMapping[0] = 0;
    // 將質數對應的索引 1，數字 1 設定為不是質數
    numberPrimesMapping[1] = 0;
    // 質數數量
    var primesNumberCount = 0;
    for (var checkNumber = 2; checkNumber < checkCountPrimesNumber; checkNumber++) {
        // 從 2 開始檢查是不是質數，直到小於指定的數字
        if (!numberPrimesMapping[checkNumber]) {
            // 如果是質數，跳過不檢查
            continue;
        }
        // 此數字是質數，數量++
        primesNumberCount++;
        // 將此質數後方的倍數數字設定為不是質數
        for (var j = checkNumber * checkNumber; j < checkCountPrimesNumber; j += checkNumber) {
            numberPrimesMapping[j] = 0;
        }
    }
    return primesNumberCount;
}

TypeScript

function countPrimes(checkCountPrimesNumber: number): number {
    if (checkCountPrimesNumber < 3) {
        // 假如傳入的數字是小於 3，所以可能是 1 或 2，但找不到小於 1 或 2 的質數，所以直接回傳 0
        return 0;
    }
    // 整數質數對應表，預設都是質數(1: 質數，0: 不是質數)
    let numberPrimesMapping = new Array(checkCountPrimesNumber).fill(1);

    // 將質數對應的索引 0，數字 0 設定為不是質數
    numberPrimesMapping[0] = 0;
    // 將質數對應的索引 1，數字 1 設定為不是質數
    numberPrimesMapping[1] = 0;

    // 質數數量
    let primesNumberCount = 0;
    for (let checkNumber = 2; checkNumber < checkCountPrimesNumber; checkNumber++) {
        // 從 2 開始檢查是不是質數，直到小於指定的數字
        if (!numberPrimesMapping[checkNumber]) {
            // 如果是質數，跳過不檢查
            continue;
        }
        // 此數字是質數，數量++
        primesNumberCount++;
        // 將此質數後方的倍數數字設定為不是質數
        for (let j = checkNumber * checkNumber; j < checkCountPrimesNumber; j+=checkNumber ) {
            numberPrimesMapping[j] = 0;
        }

    }

    return primesNumberCount;
};

參考資料