5.10 如何高效寻找素数

本文对应的力扣题目：

除了1和自身外，不能被其他自然数整除的数。

204.计数质数

那么现在让你实现一个函数，输入一个正整数 n，函数返回区间 [2, n) 中素数的个数，函数签名如下：

int countPrimes(int n);

完整的最终代码：

int countPrimes(int n) {
    // 传入的非负整数，存放到数组中
    boolean[] isPrime = new boolean[n];
    // 全部传入为True
    Arrays.fill(isPrime, true);
    for (int i = 2; i * i < n; i++) 
        // 如果为数组,删除所有数组的倍数
        if (isPrime[i]) 
            // 去除数组的倍数
            for (int j = i * i; j < n; j += i) 
				// 删除操作
                isPrime[j] = false;
    // 统计有几个true
    int count = 0;
    // 遍历true的个数
    for (int i = 2; i < n; i++)
        // 如果为true，count+1
        if (isPrime[i]) count++;
    
    return count;
}

// 评论区代码
var countPrimes = function(n) {
    let count = 0;
    let signs = new Array(n);
    // 8位无符号的整型数组
    // let signs = new Uint8Array(n);
	// 遍历2后面所有的数
    for (let i = 2; i < n; i++) {
        // 如果不是 存放遍历结果的数组signs中 前一位
        if (!signs[i - 1]) {
            // 统计到质数，数量+1
            count++;
			// 继续遍历查找i后面 i的倍数[4,6,8,10...],
            for (let j = i*i; j <= n; j += i) {
                // 找到后标记为true
                signs[j - 1] = true;
            }
        }
    }
    return count;
};

// 官方提供代码
var countPrimes = function(n) {
    // 接收非负整数,用1来填充数组中起始位置
    const signs = new Array(n).fill(1);
    const primes = [];
    for(let i = 2; i < n; ++i){
        if(signs[i]){
			primes.push(i);
        }
        // 遍历 j的值小于primes长度和数组中的值小于n 
        for(let j = 0; j < primes.length && i * primes[j] < n; ++j){
            signs[i* primes[j]] = 0;
			if(i % primes[j] === 0){
				break;
            }
        }
    }
    return primes.length;
};