[ LeetCode ] [ Kotlin ] - 204. Count Primes 難度 ★ (Kotlin速度第一名 ) @ 西瓜是肥貓

先看看題目：

204. Count Primes

Easy

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.

簡單的說就是找出0 到 n整數以內有幾個質數，這一題我一開始自己寫是速度相當慢的，後來參考了別人的答案豁然開朗，其思路就是不要一個數一個數去徹底檢查，而是想辦法做出範圍內的查表，把範圍內被可以被小數字乘的數先找出來，歸類為非質數，每個數都用同張表去查，會省去相當多的時間，來看看程式碼：

class Solution {
    fun countPrimes(n: Int): Int {
        val notPrime = BooleanArray(n)
        var count = 0
        for (i in 2 until n) {
            if (notPrime[i] == false) {
                count++
                var j = 2
                while (i * j < n) {
                    notPrime[i * j] = true
                    j++
                }
            }
        }
        return count
    }
}

最後附上通關時間：

截圖 2020-09-01 上午11.58.39