一、题目粗心
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月完结了贪婪算法的题，开启“巧解数学问题”类的题目