计数质数[枚举 -＞ 空间换时间]

前言

对于枚举法/暴力法，都是有着较高的时间复杂度。原因可能是没有用到题目已给的显示条件/需要挖掘的隐式个性，也有可能是很多重复计算，需要空间记录从而缓解时间消耗。

一、计数质数

二、枚举->空间换时间

1、暴力枚举

// 计数质数
public class CountPrimes {
    
    /* target：给定一个非负整数n,返回小于n的所有质数。 什么是质数？除了1和本身，没有其他因数 的大于1的自然数。 */
    // 暴力解
    public int countPrimes(int n) {
    
        // 特殊情况，特殊处理。
        if (n < 2) return 0;

        // 判定每个数是否为素数。
        int ans = 1;// 先把2算。
        for (int i = 3; i < n; i++) if (isTrue(i)) ++ans;

        return ans;
    }

    private boolean isTrue(int n) {
    
        // 剪枝，只需要验证到sqrt(n)即可，两边镜像。如 2 * 4 == 8 == 4 * 2
        int bound = (int) Math.sqrt(n);
        for (int i = 2; i <= bound; i++) if (n % i == 0) return false;

        return true;
    }
}

2、空间换时间

class CountPrimes2 {
    
    /* target：给定一个非负整数n,返回小于n的所有质数。 什么是质数？除了1和本身，没有其他因数 的大于1的自然数。 暴力解超时，如果能把非质数挑出来，那么剩下的就算质数了，非质数都是 质数与质数/非质数相乘。 为什么没有非质数 与这些相乘？因为非质数可被拆解成一大一小的数，而小的数已经把后面所有倍数 的非质数标记了。如 8 == 2 * 4，8 * n == 2 * (4 * n) 可将质数的每个倍数都标记为 非质数，然后往后走，没被标记的则是质数，再把该质数的所有倍数（除前面已经标记的，所以从i * i开始）标记为非质数。 */
    // 空间换时间，记录非素数，寻找素数。
    public int countPrimes(int n) {
    
        // 特殊情况，特殊处理。
        if (n < 2) return 0;

        // 标记非质数，寻找质数个数。
        boolean[] isNotPrim = new boolean[n];
        int ans = 0;
        for (int i = 2; i < n; i++) {
    
            if (!isNotPrim[i]) {
    
                // 未被标记成非质数，则其是质数。
                ++ans;
                // 标记非质数。
                // 从i * i开始，毕竟轮到i-1时，它乘过i,i+1,...
                if (i < Math.sqrt(n)) for (int j = i * i; j < n; j += i) isNotPrim[j] = true;
            }
        }

        return ans;
    }
}

总结

1）从暴力枚举，到空间换时间（利用题目隐式特征）。

参考文献

[1] LeetCode 计数质数