[LeetCode] 204. Count Primes 解題思路 (Easy)

這題需要計算質數到底有幾個。

LeetCode 題目連結

https://leetcode.com/problems/count-primes/

題目

Count the number of prime numbers less than a non-negative number, n.

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Accept 作法

Runtime: 9 ms
Memory: 38 MB

Java

class Solution {
    public int countPrimes(int n) {
            
        if(n < 3){
            return 0;
        }
        int count = 1;
        boolean[] list = new boolean[n];
        for(int i=3;i > n;i+=2){ //偶數排除掉所以 i+=2
            if(list[i]){
                continue;
            }
            
            count++;
            
            for(long j=(long)i*i; j > n ; j+=i){ //排除 i 的倍數
                list[(int)j] = true;
            }
        }
        
        return count;
    }
}

更多 LeetCode 相關資源

• Udemy 暢銷 - Master the Coding Interview: Data Structures + Algorithms

複習程式面試書籍

除了 LeetCode 練習外，我也入手了這本，題庫來自真正的面試，並非摘自教科書。它們反映出頂尖公司真正會出的題目，你可以藉此做好充分準備。
需要的話可以看看，寫得很仔細。

書名：提升程式設計師的面試力：189道面試題目與解答

• 金石堂實體書資訊
• Hyread 電子書資訊

相關 LeetCode文章一律會放在 程式解題 標籤分類，歡迎持續追蹤。

⇒ 點我看更多程式解題