计数质数
难度:
标签:
题目描述
给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
示例 1：
输入：n = 10 输出：4 解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0 输出：0
示例 3：
输入：n = 1 输出：0
提示：
0 <= n <= 5 * 106
代码结果
运行时间: 54 ms, 内存: 16.2 MB
/*
* 思路：
* 使用Java Stream和埃拉托斯特尼筛选法来计算质数数量。
* 我们先生成一个从2到n-1的IntStream，然后过滤掉所有非质数。
* 最后，返回过滤后元素的数量。
*/
import java.util.stream.IntStream;
public class CountPrimesStream {
public int countPrimes(int n) {
if (n <= 2) return 0;
boolean[] isPrime = new boolean[n];
for (int i = 2; i < n; i++) isPrime[i] = true;
for (int i = 2; i * i < n; i++) {
if (isPrime[i]) {
for (int j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}
}
return (int) IntStream.range(2, n).filter(i -> isPrime[i]).count();
}
}解释
方法:
此题解采用了经典的埃拉托斯特尼筛法（Sieve of Eratosthenes）来寻找所有小于非负整数 n 的质数。首先，算法创建一个布尔数组 isNumPrimes 来跟踪每个数是否为质数，初始化时假设所有数都是质数。接着，通过遍历2到n的每个数，如果发现一个数i是质数（isNumPrimes[i]为True），则将i的所有倍数设置为非质数（False），从而筛选掉非质数。这里需要注意的是，筛选从i*i开始，因为小于i*i的倍数在之前已经被筛选过了。最终，数组中为True的位置表示该位置的索引是质数，通过计数这些位置得到小于n的所有质数的数量。
时间复杂度:
O(n log log n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在筛法中，对于每个质数i，筛选开始于i*i而不是2*i或i+i？
▷🦆
在大于平方根n的数字上，算法是否还需要检查其是否为质数？
▷🦆
给定初始化时布尔数组isNumPrimes的所有值都设为True，这种做法对空间复杂度有何影响？
▷相关问题
丑数
丑数 就是只包含质因数 2、3 和 5 的正整数。
给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：n = 6 输出：true 解释：6 = 2 × 3
示例 2：
输入：n = 1
输出：true
解释：1 没有质因数，因此它的全部质因数是 {2, 3, 5} 的空集。习惯上将其视作第一个丑数。
示例 3：
输入：n = 14
输出：false
解释：14 不是丑数，因为它包含了另外一个质因数 7 。
提示：
-231 <= n <= 231 - 1