中等 · 巢狀迴圈
數素數個數
n 以內有多少個素數?第一道“內層迴圈才是主角”的題——也是 break 第一次成為效能問題而不只是風格。
題目
輸入:一個整數 n(0 ≤ n ≤ 10⁶)。
輸出:滿足 p ≤ n 的素數 p 的個數。
樣例:
| 輸入 | 輸出 |
|---|---|
10 | 4 |
100 | 25 |
你的解答
"用我的輸入試跑"的自定義輸入
判題完全在你的瀏覽器裡對隱藏測試執行。程式碼隨打隨存(本地)。Ctrl+Enter 判題。
卡住了?提示
提示 1 —— 複用素數判定
內層判斷就是素數判定那道題:試除到 √i,找到第一個因子就 break。外面套一層 2..n 的迴圈,數倖存者。
提示 2 —— break 為什麼重要
不寫 break,每個數都要試完所有因子;寫了,大多數數除一兩次就退出。n = 10⁶ 時這是"秒級"和"超時"的差別。
解答(先自己試!)
int n = int.Parse(Console.ReadLine());
int count = 0;
for (int i = 2; i <= n; i++)
{
bool prime = true;
for (int d = 2; d * d <= i; d++)
{
if (i % d == 0) { prime = false; break; }
}
if (prime) count++;
}
Console.WriteLine(count);再進一步是埃拉托色尼篩法——用布林陣列代替試除,把 O(n√n) 變成 O(n log log n)。下一題:水仙花數。