先看看題目：
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
}
}最後附上通關時間：
文章標籤
全站熱搜
留言列表
讀書心得 (1)
{{ article.title }}
