質數 Prime

質數 Prime
Categories:
Tags:

埃拉托斯特尼篩法

質數的所有倍數數字都不是質數，所以當一檢查到質數，可以將這個質數後方的所有倍數數字設定為不是質數

質數 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
質數 x 倍數 不是值數數值
4 x 2 8
4 x 3 12
4 x 4 16
4 x 5 20

演算法流程

因為至少必須要將檢查數次方後面的數字設定為非質數，所以設定的斷點可以小於 Math.ceil(Math.sqrt(n)); 開根號無條件進位即可

Prime

情境程式

計算指定數字小的質數數量

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;
};
超過全部數字開根號的數字不計算
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 finalCheckCountPrimesNumber = Math.ceil(Math.sqrt(checkCountPrimesNumber));
    // 質數數量
    let primesNumberCount = 0;
    for (let checkNumber = 2; checkNumber < finalCheckCountPrimesNumber; checkNumber++) {
        // 從 2 開始檢查是不是質數，直到小於指定的數字
        if (!numberPrimesMapping[checkNumber]) {
            // 如果是質數，跳過不檢查
            continue;
        }
        // 此數字是質數，數量++
        primesNumberCount++;
        // 將此質數後方的倍數數字設定為不是質數
        for (let j = checkNumber * checkNumber; j < checkCountPrimesNumber; j+=checkNumber ) {
            numberPrimesMapping[j] = 0;
        }
    }

    // 計算剩餘的質數數量
    for (let checkNumber = finalCheckCountPrimesNumber; checkNumber < checkCountPrimesNumber; checkNumber++) {
        if (numberPrimesMapping[checkNumber]) {
            // 此數字是質數，數量++
            primesNumberCount++;
        }
    }

    return primesNumberCount;
};

LeetCode

題目 說明
204. Count Primes 傳入一個整數 n，回傳小於整數 n 的所有質數數量

參考資料