LeetCode-计数质数

迷南。 2021-09-23 14:32 313阅读 0赞

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

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

解题思路：

1、暴力破解

验证一个数是否为质数有很多方法。最容易想到的就是暴力破解，采用暴力计算一步步碾压过去的方法。虽然不是最优的，但是对于我们解题是最有效的。

public boolean isPrime(int n){
            for(int i = 2 ; i*i <= n ; i++){
                if(n % i == 0){
                    return false;
                }
            }
            return true;
        }
    
        /**
         * @param n
         * @return
         */
        public int countPrimes(int n) {
            int count = 0;
            for(int i = 2; i < n; i++){
                if(isPrime(i)){
                    count++;
                }
            }
            return count;
        }

通过遍历2-n之间的数，判断是否存在整除的元素存在，存在则不是，反之则是。毕竟是暴力破解嘛，效率上肯定不会很满意，使用 isPrime 函数来辅助就很不高效，而且算法也存在冗余。在输入值很大的情况下，直接超时警告。

如何判断一个数是不是质数，只需稍微改动 isPrime 代码：

boolean isPrime(int n) {
        for (int i = 2; i * i <= n; i++)
            ...
    }

换句话说，i不需要遍历到n，只需要到sqrt(n)即可。举个栗子，假设n=8

8=2*4
    8=sqrt(8)*sqrt(8)
    8=4*2

可以看到最前面和最后面是反过来的，而临界点就是sqrt(n)。换句话说就是如果在\[2,sqrt(n)\]区间上不存在可整除因子，即可以断定是质数了。

**2、高效实现：**

高效解决这个问题核心思想是常规思想反着来：

从2开始，2是质数，那么2的倍数都不可能是质数了。2\*2 = 4，2\*3 = 6， 2\*4 = 8 ...

从3开始，3是质数，那么3的倍数也都不可能是质数了。3\*2 = 6,3\*3 = 9，3\*4 = 12...

所以到现在是不是明白这个算法的逻辑呢？

int countPrimes(int n) {
        boolean[] isPrim = new boolean[n];
        // 将数组都初始化为 true
        Arrays.fill(isPrim, true);
    
        for (int i = 2; i < n; i++) 
            if (isPrim[i]) 
                // i 的倍数不可能是素数了
                for (int j = 2 * i; j < n; j += i) 
                        isPrim[j] = false;
        
        int count = 0;
        for (int i = 2; i < n; i++)
            if (isPrim[i]) count++;
        
        return count;
    }

如果上面的代码能够理解，那么已经掌握了整体思路，但还有两个细微的地方可以优化。

刚才判断一个数是否是质数的isPrime函数，由于因子对称性，只需要遍历\[2,sqrt(n)\]就够了。同样外层循环也是一样：

for (int i = 2; i * i < n; i++) 
        if (isPrim[i]) 
            ...

除此之外，内层的循环也是可以优化的。之前做法：

for (int j = 2 * i; j < n; j += i) 
        isPrim[j] = false;

这样把i的整数倍都标记为false，但是仍然存在计算冗余。可以稍微优化一下，让j从i的平方开始遍历：

for (int j = i * i; j < n; j += i) 
        isPrim[j] = false;

这样，质数计算的算法就十分高效了，其实还有个名字，叫Sieve of Eratosthenes。。给出完整最终代码：

/*
        Sieve of Eratosthenes 算法
         */
        public static int countPrimes3(int n) {
            boolean[] isPrim = new boolean[n];
            Arrays.fill(isPrim, true);
            for (int i=2;i*i<n;i++) {
                if (isPrim[i]) {
                    for (int j = i*i;j<n;j+=i) {
                        isPrim[j] = false;
                    }
                }
            }
            int count = 0;
            for (int k=2;k<n;k++) {
                if (isPrim[k]) {
                    count++;
                }
            }
            return count;
        }

以上就是质数算法相关的全部内容。感觉有么有很简单的样子![format_png][]![format_png][]![format_png][]

--------------------

辛苦大佬看完，有兴趣的话可以关注下公众号，共同学习进步：

![20191231084636319.jpg][]

[format_png]: /images/20210923/040fd2a0b63d4c1c8bb4c25d009dd56e.png
[20191231084636319.jpg]: /images/20210923/4cefd106d79f4ef5b62b3778269360d5.png