前言说明
算法学习，日常刷题记录。
题目连接
题目内容
统计所有小于非负整数n的质数的数量。
示例1:
输入：n = 10
输出：4
解释：小于10的质数一共有4个, 它们是2, 3, 5, 7。
示例2:
输入：n = 0
输出：0
示例3:
输入：n = 1
输出：0
提示：
0 <= n <= 5 * 10^6
分析过程
按照传统的方法，通过从2开始遍历到n - 1，逐个判断是否为质数，统计数量。
因为从3开始，质数肯定是奇数，所以遍历时每次自增2，减少遍历的次数。
而判断每一个数是否为质数时，也只需要遍历到这个数的平方根即可，因为一个数的因数不可能大于它的平方根。
所以代码如下：
class Solution {
public int countPrimes(int n) {
if (n < 3) {
// 若n小于3，统计的是小于2的质数，因为没有小于2的质数，所以结果为0
return 0;
} else {
// 质数数量，初始数量为1，因为2是质数，后面的for循环从3开始循环了
int num = 1;
// 从3开始循环判断，每次自增2，因为偶数不是质数，不用判断
for (int i = 3; i < n; i += 2) {
// 是否为质数
boolean isPrime = true;
// 从3循环到这个数的平方根
for (int j = 3; j * j <= i; j += 2) {
if (i % j == 0) {
// 若能被除尽，则不是质数
isPrime = false;
break;
}
}
if (isPrime) {
// 质数数量加1
++num;
}
}
return num;
}
}
}
但是提交结果显示运行超时。
运行结果
我们考虑用埃氏筛算法，如果x是质数，那么2x，3x…一定不是质数。
因此我们可以反过来判断，判断合数，剩下的就是质数。
我们可以用一个布尔数组来保存n之前的数，标记每一个数是质数还是合数。
如果找到了一个质数，那么质数从2倍开始遍历到n倍，直到小于n，因为x是质数，那么x的倍数一定不是质数，所以遍历到的都是合数，全部标记为true。
那有没有可能出现，一个合数被标记为质数，即false呢？
我们可以设想，假如有一个合数被标记为false了，那么合数肯定是等于它之前的某个质数的整数倍的，但是我们在之前就已经把所有的质数的整数倍判断过一次了，所以如果是合数，肯定会被标记起来，标为true。
所以，不会出现一个合数被标记为质数。
解答代码
所以需要用空间换时间，使用埃氏筛算法，解答代码如下：
class Solution {
public int countPrimes(int n) {
// 使用埃氏筛算法
// 定义质数数量
int count = 0;
// 定义布尔数组，保存n之前每个数是否为质数，false表示质数，true表示合数
boolean[] flag = new boolean[n];
// 从2开始遍历到n-1
for (int i = 2; i < n; i++) {
if (!flag[i]) {
// 若i为0，找到质数，质数数量加1
++count;
// 质数从2倍开始遍历到n倍，直到小于n，如果x是质数，那么2x，3x…一定不是质数，所以遍历到的都是合数，全部标记为true
for (int j = i + i; j < n; j += i) {
flag[j] = true;
}
}
}
// 这里省去了对每一个数从2开始逐个判断是否整除来判断质数，直接标记合数，剩下的就是质数
return count;
}
}
提交结果
执行用时51ms，时间击败59.83%的用户，内存消耗41.7MB，空间击败65.44%的用户。
运行结果
原文链接
原文链接：计数质数
网友评论