我最近在leetcode上擼了一個小算法膘螟，雖然已經(jīng)工作了五年成福，當看到每次代碼提交后排名的提升碾局，內(nèi)心依然很有成就感荆残。題目比較簡單，求小于n的素數(shù)個數(shù)净当，素數(shù)也叫質(zhì)數(shù)内斯，具有以下特點：

• 正整數(shù)
• 只能被1和本身整除
• 1既不是素數(shù)也不是合數(shù)，所以最小的素數(shù)是2

根據(jù)上面的特點像啼，我們還可以推斷出：

• 除了2俘闯，其它的素數(shù)都是奇數(shù)

依據(jù)這一點，我們可以寫出下面的實現(xiàn)：

class Solution {
    public int countPrimes(int n) {
        if (n < 3) {
            return 0;
        }
        int count = 1;// 2
        for (int i = 3; i < n; i += 2) {
            // 只判斷奇數(shù)是不是素數(shù)
            boolean isPrime = true;
            for (int j = 3; j * j <= i; j += 2) {
                // 奇數(shù)不可能被偶數(shù)整除忽冻，所以只試除奇數(shù)
                if (i % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                count++;
            }
        }
        return count;
    }
}

j * j <= i相當于j <= Math.sqrt(i)真朗，但速度會快一點，那為什么只需要判斷到√i呢僧诚，因為對于一個非素數(shù)(合數(shù))遮婶，其最小約數(shù)(除1外)必小于等于其平方根。

設(shè)k為最小約數(shù)

class Solution {
    public int countPrimes(int n) {
        if (n < 3) {
            return 0;
        }
        int count = 0;
        int[] primes = new int[n / 2];
        for (int i = 3; i < n; i += 2) {
            // 只判斷奇數(shù)是不是素數(shù)
            boolean isPrime = true;
            for (int j = 0; j < count && primes[j] * primes[j] <= i; j++) {
                // 只試除素數(shù)
                if (i % primes[j] == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                primes[count++] = i;
            }
        }
        return count + 1;// 2
    }
}

埃拉托斯特尼篩法

篩選的過程是先篩掉非素數(shù)急凰，針對本文的題目，每篩掉一個，素數(shù)數(shù)量-1即可抡锈，上面說過素數(shù)的一個特點疾忍，除了2，其它的素數(shù)都是奇數(shù)床三，所以我們只需在奇數(shù)范圍內(nèi)篩選就可以了一罩。

class Solution {
    public int countPrimes(int n) {
        if (n < 3) {
            return 0;
        }
        int count = n / 2;// 篩掉一半偶數(shù)
        boolean[] notPrime = new boolean[n];
        for (int i = 3; i * i < n; i += 2) {// 只篩3≤i<√n奇數(shù)
            if (!notPrime[i]) {        
                // 篩掉素數(shù)的奇數(shù)倍數(shù)
                for (int j = i * i; j < n; j += 2 * i) {// 從i*i開始篩
                    if (!notPrime[j]) {
                        notPrime[j] = true;
                        count--;
                    }
                }
            }
        }
        return count;
    }
}

版權(quán)聲明
本博客所有的原創(chuàng)文章找蜜，作者皆保留版權(quán)饼暑。轉(zhuǎn)載必須包含本聲明，保持本文完整洗做，并以超鏈接形式注明作者高爽和本文原始地址：http://www.reibang.com/p/d6736b492720弓叛。