计数质数

发表于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

LeetCode每日一题，204. Count Primes

先看题目描述

DobLkV.png

大意就是给定一个数字 n，让我们返回小于 n 的质数个数

算法和思路

暴力法

第一反应就是从 2 开始遍历小于 n 的每个数，判断该数是否是质数，若该数是质数，则将 ans + 1，最后返回 ans 即可(暴力法跑超时了，但有的时候能提交成功)

埃式筛

这个方法以前从没接触过，看题解才知道这个方法

我们考虑这样一个事实：如果 x 是质数，那么大于 x 的 x 的倍数 2x,3x,… 一定不是质数，因此我们可以从这里入手

我们设 isPrime[i] 表示数 i 是不是质数，如果是质数则为 1，否则为 0。从小到大遍历每个数，如果这个数为质数，则将其所有的倍数都标记为合数（除了该质数本身），即 0，这样在运行结束的时候我们即能知道质数的个数

这种方法的正确性是比较显然的：这种方法显然不会将质数标记成合数；另一方面，当从小到大遍历到数 x 时，倘若它是合数，则它一定是某个小于 x 的质数 y 的整数倍，故根据此方法的步骤，我们在遍历到 y 时，就一定会在此时将 x 标记为 isPrime[x] = 0。因此，这种方法也不会将合数标记为质数

当然这里还可以继续优化，对于一个质数 x，如果按上文说的我们从 2x 开始标记其实是冗余的，应该直接从 x⋅x 开始标记，因为 2x,3x,… 这些数一定在 x 之前就被其他数的倍数标记过了，例如 2 的所有倍数，3 的所有倍数等

算法源码

暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int countPrimes(int n) {
        int ans = 0;
        for (int i = 2; i < n; ++i) {
            ans += isPrime(i) ? 1 : 0;
        }
        return ans;
    }

    public boolean isPrime(int x) {
        for (int i = 2; i * i <= x; ++i) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}

注意：在判断一个数字是否是质数的方法中，for 循环的界限使用 i * i <= x，而不是使用 i <= Math.sqrt(x)，速度会更快

埃式筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int countPrimes(int n) {
        int ans = 0;
        int[] isPrime = new int[n];
        Arrays.fill(isPrime, 1);
        for (int i = 2; i < n; ++i) {
            if (isPrime[i] > 0) {
                ans += isPrime[i];
                if ((long) i * i < n) {
                    for (int j = i * i; j < n; j += i) {
                        isPrime[j] = 0;
                    }
                }
            }
        }
        return ans;
    }
}