leetcode 204. Count Primes 计数质数 (Easy)
LeetCode count 计数 Easy 质数
2023-09-11 14:22:52 时间
一、题目大意
https://leetcode.cn/problems/count-primes
给定整数 n ,返回 所有小于非负整数 n 的质数的数量 。
示例 1:
输入:n = 10
输出:4
解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2:
输入:n = 0
输出:0
示例 3:
输入:n = 1
输出:0
提示:
- 0 <= n <= 5 * 106
二、解题思路
输入一个整数,输出也是一个整数,表示小于输入数的质数的个数。
埃拉托斯特尼筛法,是判断一个整数是否是质数的方法。并且它可以在判断一个整数n时,同时判断所小于n的整数,因此非常适合这个问题。其原理是:从1到n遍历,假设当前遍历到m,则把所有小于n的、且是m的倍数的整数标为和数;遍历完成后,没有被标为和数的数字即为质数。
三、解题方法
3.1 Java实现
public class Solution {
public int countPrimes(int n) {
if (n <= 2) {
return 0;
}
boolean[] prime = new boolean[n];
Arrays.fill(prime, true);
int i = 3;
int sqrtn = (int) Math.sqrt(n);
// 偶数一定不是质数
int count = n / 2;
while (i <= sqrtn) {
// 最小质因子一定小于等于开方数
for (int j = i * i; j < n; j += 2 * i) {
// 避免偶数和重复遍历
if (prime[j]) {
count--;
prime[j] = false;
}
}
do {
i+= 2;
// 避免偶数和重复遍历
} while (i <= sqrtn && !prime[i]);
}
return count;
}
}
四、总结小记
- 2022/8/1 7月结束了贪心算法的题,开启“巧解数学问题”类的题目
相关文章
- Leetcode 之Count and Say(35)
- Java实现 LeetCode 822 翻转卡片游戏(暴力)
- Java实现 LeetCode 515 在每个树行中找最大值
- Java实现 LeetCode 423 从英文中重建数字
- Java实现 LeetCode 95 不同的二叉搜索树 II(二)
- Java实现 LeetCode 5 最长回文子串
- 【LeetCode算法-38】Count and Say
- [Javascript] Using console.count to Count Events
- 【二叉搜索树】LeetCode 96. 不同的二叉搜索树【中等】
- 【LeetCode算法-38】Count and Say
- 494. 目标和——【Leetcode每日刷题】
- leetcode_Jump Game II
- 【LeetCode-python】第2题 两数相加
- 【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点
- 【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色