[LeetCode] 204. Count Primes

轉自LeetCode

Description:

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

<Solution>

這邊有個解題的影片 https://www.youtube.com/watch?v=eKp56OLhoQs

主要想法如下

• 先從 2 這個質數開始，然後把所有小於 n 的 2 的倍數，都標記起來不計算

• 一個加速的方式是，只有小於等於 sqrt(n) 的質數，才需要去把該質數的倍數都去劃掉(詳細解釋可看影片)

code 如下

Java

C++


kotlin