关于leetcode:leetcode-204-Count-Primes-计数质数-Easy

一、题目粗心

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