leetcode 204. Count Primes 计数质数 (Easy)
一、题目大意
https://leetcode.cn/problems/count-primes
给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
示例 1：
输入：n = 10示例 2：
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
输入：n = 0示例 3：
输出：0
输入：n = 1提示：
输出：0
- 【leetcode 204. Count Primes 计数质数 (Easy)】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|[leetcode 算法练习] - 14. 最长公共前缀
- LeetCode|LeetCode 探索初级算法-数组（03 旋转数组-20200316）
- leetcode|leetcode 665. Non-decreasing Array 非递减数列(中等)
- #|LeetCode每日一题——1161. 最大层内元素和
- #|LeetCode每日一题——593. 有效的正方形
- #|Leetcode每日一题——三个无重叠子数组的最大和
- Hadoop-Eclipse|Hadoop-Eclipse mapreduce测试WordCountMapReduce
- 240、搜索二维矩阵|240、搜索二维矩阵 II | 算法（leetcode，附思维导图 + 全部解法）300题
- 双指针的妙用——leetcode11盛最多水的容器
- leetcode|leetcode 763. Partition Labels 划分字母区间(中等)