A man is like a novel: until the very last page you don't know how it will end.
人就像一部小说：除非翻到最后一页，否则你不知道TA有怎样的结局。
问题描述
来源：LeetCode第204题
难度：简单
统计所有小于非负整数n的质数的数量。
示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0
输出：0
示例 3：
输入：n = 1
输出：0
提示：
0 <= n <= 5 * 10^6
解题思路
这题让求质数的个数，质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
我们知道任何合数都可以分解成m个质数的乘积，比如
12=2*2*3；
100=2*2*5*5
……
我们反过来想，任何一个质数比如a，他的n（n>=2）倍一定不是质数，也就是a*2，a*3……都不在是质数。我们可以申请一个长度为length的数组用来存储对应的数是不是质数。然后在用一个变量count来统计质数的个数，如果是合数就不需要统计，如果是质数，count就加1，然后再把质数的2倍，3倍……都标记为非质数，原理比较简单，我们来看下代码
1public int countPrimes(int n) {
2 //标记合数
3 boolean[] composite = new boolean[n];
4 int count = 0;//统计质数的个数
5 for (int i = 2; i < n; i++) {
6 //如果是合数就不需要统计
7 if (composite[i])
8 continue;
9 count++;
10 //到这一步说明是质数，直接让他的2倍，
11 // 3倍……都标记为合数
12 for (int j = i; j < n; j += i)
13 composite[j] = true;
14 }
15 return count;
16}
联系客服
