LeetCode 204.计数质数(简单)
发布时间：2023-09-08 09:18:19 272 相关标签：
题目描述
统计所有小于非负整数n的质数的数量。
示例 1
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2
示例 3
提示
题目分析
一看这题目不是对我们来说很简单嘛，直接写一个判断一个数是否为素数的方法，然后直接循环，是素数的就累计起来就行了，于是乎有了下面的解法。
class Solution {
// 判断是否为素数的方法
public boolean isPrime(int n) {
for (int i = 2; i * i < n; ++i) {
if (n % i == 0) {
return false;
}
}
return true;
}
public int countPrimes(int n) {
// 素数个数
int count = 0;
// 遍历所有数判断是否为素数
for (int i = 2; i < n; ++i) {
if (isPrime(i)) {
count++;
}
}
return count;
}
}但很遗憾的告诉你，这样提交后会超时的。那要怎么办呢？如果有看我前些天写的操作系统实验的推文的同学可能就会想起来，有一个实验要求我们实现输出0-35的素数的程序，从中可以获得些许灵感，特别是实验提供下面的那张图。
之外，数组中所有都初始化为true，即表示它们都为素数。然后定义一个变量存放素数个数，初始都为素数，但要减去0和1。接下来遍历数组，遍历到的第一个一定是素数，获取此素数，再次遍历数组，把数值为此数倍数的数全部标记为false，即非素数，并把素数的统计值相应减去。然后继续重复执行上述过程，即可统计到素数的个数。
题解一
执行用时: 62 ms
内存消耗: 41.8 MB
class Solution {
public int countPrimes(int n) {
// 如果 n 小于 3 则没有符合条件的素数返回0
if (n < 3) {
return 0;
}
// 新建标记数组，true 表示当前索引为素数
boolean[] prime = new boolean[n];
// 让数组每个值都为true，默认每个数都为素数
Arrays.fill(prime, true);
// 变量统计素数个数，初始时都为素数，把 0 和 1 减掉
int count = n - 2;
// 循环 2 到 n - 1 把非素数标记出来
for (int i = 2; i < n; ++i) {
// 如果是素数
if (prime[i]) {
// 循环把是此数的倍数的数标记为非素数
for (int j = 2 * i; j < n; j += i) {
if (prime[j]) {
prime[j] = false;
// 把重新标记为非素数的减掉
--count;
}
}
}
}
// 返回素数个数
return count;
}
}题解二
执行用时: 23 ms
内存消耗: 42 MB
// 题解一的优化版本
class Solution {
public int countPrimes(int n) {
// 如果 n 小于 3 则没有符合条件的素数返回0
if (n < 3) {
return 0;
}
// 新建标记数组，true 表示当前索引为素数
boolean[] prime = new boolean[n];
// 让数组每个值都为true，默认每个数都为素数
Arrays.fill(prime, true);
// 变量统计素数个数，初始时都为素数，去除偶数，把1换成2，因为2是质数
int count = n >> 1;
// 循环把非素数标记出来
for (int i = 3; i * i < n; i += 2) {
// 如果是素数
if (prime[i]) {
// 循环把是此数的倍数的数标记为非素数
for (int j = i * i; j < n; j += (i << 1)) {
if (prime[j]) {
prime[j] = false;
// 把重新标记为非素数的减掉
--count;
}
}
}
}
// 返回素数个数
return count;
}
}
题目来源:力扣(LeetCode)
文章来源： https://blog.51cto.com/u_15891283/5886608
特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。
举报
