解題說明
Count Primes
題目描述：給定整數 n，回傳所有嚴格小於 n 的質數個數。
解題思路：使用埃拉托斯特尼篩法（Sieve of Eratosthenes）。建立大小為 n 的布林陣列 is_prime，初始全設為 true。從 2 開始，對每個質數 p，將 p² 以及 p² + p、p² + 2p...等所有 p 的倍數標記為非質數（從 p² 開始是因為更小的倍數已在之前被標記）。外層迴圈只需跑到 √n，因為若 n 有因數大於 √n，另一因數必小於 √n 而已被篩除。此方法是計算質數最高效的經典算法。
C++ 解法
複雜度分析
時間複雜度：O(n log log n) — 埃拉托斯特尼篩法的理論時間複雜度，遠優於逐一判斷的 O(n√n)。
空間複雜度：O(n) — 需要大小為 n 的布林陣列存放篩選結果。
虛擬碼
1. If n < 2, return 0
2. Create boolean array is_prime[0..n-1], initialize all to true
3. Set is_prime[0] = is_prime[1] = false
4. For i from 2 to sqrt(n):
If is_prime[i] is true:
For j from i*i to n-1 (step i):
Set is_prime[j] = false
5. Count and return number of true values in is_prime其他解法
逐一判斷法：對每個數從 2 到 √n 逐一試除判斷是否為質數。時間 O(n√n)，實作簡單但對大 n 效率極差。
線性篩（歐拉篩）：確保每個合數只被其最小質因數篩掉一次，時間嚴格 O(n)，但常數因子較大，程式碼較複雜，一般情況下埃氏篩已足夠。
分段篩法：將範圍分成大小約 √n 的區段分別篩選，可將空間降至 O(√n)，適合 n 極大的情況。
延伸思考
- 埃拉托斯特尼篩法的時間複雜度為何是 O(n log log n) 而非 O(n log n)？能否給出直觀解釋？
- 如果要計算
[L, R]範圍內的質數個數（L 可能很大，但 R-L 較小），如何用分段篩法高效求解？ - 質數定理指出小於 n 的質數個數近似 n/ln(n)，這與篩法的時間複雜度有何關聯？