质数 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 的所有质数数量

参考资料