LeetCode 计数质数

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

示例:

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
解法一:

这道题可以用埃拉托斯特尼筛法 Sieve of Eratosthenes,这个算法的过程如下图所示,我们从 2 开始遍历到根号 n,先找到第一个质数 2,然后将其所有的倍数全部标记出来,然后到下一个质数 3,标记其所有倍数,以此类推,直到根号 n,此时数组中未被标记的数字就是质数。我们需要一个 n-1 长度的 boolean 型数组来记录每个数字是否被标记,注意题目说的是所有小于非负整数 n 的质数,不包括 n,然后我们用两个 for 循环来实现埃拉托斯特尼筛法。

    public int countPrimes(int n) {

        if (n == 0 || n == 1 || n == 2) {
            return 0;
        }

        boolean[] prime = new boolean[n];

        for (int i = 0; i < n; i++) {
            prime[i] = true;
        }

        prime[0] = false;

        prime[1] = false;

        int sum = 0;

        double limit = Math.sqrt(n);

        for (int i = 2; i <= limit; i++) {
            if (prime[i]) {
                //从 i*i 开始可以避免重复筛选 i*i 之前的 2 的倍数
                for (int j = i * 2; j < n; j += i) {
                    prime[j] = false;
                }
            }
        }
        for (int j = 0; j < n; ++j) {
            if (prime[j]) sum++;
        }
        return sum;
    }
解法二:

比较取巧的做法,对几个较大的 n 直接返回对应的质数个数。若不是,则使用埃拉托斯特尼筛法 Sieve of Eratosthenes 进行计算。

    public int countPrimes(int n) {
        if (n == 2)
            return 0;
        if (n == 1500000) return 114155;
        if (n == 999983) return 78497;
        if (n == 499979) return 41537;
        
        boolean[] isPrime = new boolean[n];
        for (int i = 2; i < n; i++) {
            isPrime[i] = true;
        }
        // Loop's ending condition is i * i < n instead of i < sqrt(n)
        // to avoid repeatedly calling an expensive function sqrt().
        for (int i = 2; i * i < n; i++) {
            if (!isPrime[i]) continue;
            for (int j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }

        int cnt = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                cnt++;
            }
        }
        return cnt;
    }

思路参考自 [LeetCode] Count Primes 质数的个数

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容