本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

一、题目描述

计数质数

统计所有小于非负整数 n 的质数的数量。

示例 1：

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：

输入：n = 0
输出：0
示例 3：

输入：n = 1
输出：0

提示：

0 <= n <= 5 * 106

二、思路分析

• 获得小于n的非负数中质数的个数。首先我们得知道什么叫质数（除了1和自己本身以外不能被其他数整除的叫做质数）
• 首先就是暴露破解。咋一看感觉除了暴力破解也没其他办法了。暴力实现的方式也很简单两层循环就可以解决了。

public int countPrimes(int n) {
    int total = 0;
    for (int i = 2; i < n; i++) {
        int j=2;
        for (j = 2; j < i; j++) {
            if (i % j == 0) {
                break;
            }
        }
        if (j == i) {
            total++;
        }
    }
    return total;
}
复制代码

• 之前也提到过算法考察的思维并不是解决问题。上面的暴力方法贴到leetcode上是这个结果

• 就算是leetcode通过，这种解法也不是最优的。

三、升级之路+AC代码

减少暴力次数

• 不知道大家有没有发现比如6有哪些数据相乘得到。仔细观察上图会发现在2之后其实就是重复。