计数质数

计数质数

判断一个素数很简单，代码如下，但如何高效的搜寻一个区间内的所有素数呢？

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

一个数若是可以因式分解，那么得到的两个数一定是一个大于等于√n，一个小于等于√n，所以只需遍历到√n即可
说回正题，我们要做的不是判断区间内所有数是不是素数，而是筛选结果，意思是我们判断出2是素数，那么2的倍数都不可能是素数，如果我们用一个布尔数组/集合来保存结果，那么在 k=2i,3i······ 的位置上皆为false

    public int countPrimes(int n) {
        if (n < 2) return 0;
        List<Boolean> isPrimes = new ArrayList<Boolean>
                (Collections.nCopies(n, true));
        isPrimes.set(0, false);
        isPrimes.set(1, false);
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrimes.get(i)) count++;
            for (int j = i; j < n; j += i) {
                isPrimes.set(j, false);
            }
        }
        return count;
    }

Tips:

• 用了额外的N+1的存储空间，时间复杂度是O(n/2 + n/3 + n/5 + n/7 +······）