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

参考资料