204. Count Primes - Medium

前往題目

回歸leetcode，四個月的當兵猶如一場夢，自由真好

想法

• 略過2, 3, 5, 7的倍數

思路

Sieve of Eratosthenes Algorithm

1. 從第一個質數開始(2)，並標記2的所有倍數(<n)為非質數
2. 往下一個未被標記的數字，重複步驟一
3. 直到當前數字的平方大於n，後面的數字直接看標記為質數或非質數更新結果即可

Code

class Solution {
    public int countPrimes(int n) {
        boolean[] isPrime = new boolean[n];
        //Fill with true
        for (int i = 0; i < isPrime.length; ++i) {
            isPrime[i] = true;
        }

        // The final result
        int res = 0;

        // Go through the range
        for (int i = 2; i < n; ++i) {
            if (isPrime[i] == false) continue;
            ++res;

            // Skip impossible number
            if (i < Math.sqrt(n)) {
                // Exclude current number's multiple
                for (int j = i * 2; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        return res;
    }
}