中等 · 試除法
素數判定
n 有沒有 1 和自身之外的因子?只試到 √n——而且找到一個就停。√n 這個界正是它快的原因。
題目
輸入:一個整數 n(0 ≤ n ≤ 10⁶)。
輸出:素數輸出 Yes,否則 No(0 和 1 不是素數)。
樣例:
| 輸入 | 輸出 |
|---|---|
7 | Yes |
25 | No |
你的解答
"用我的輸入試跑"的自定義輸入
判題完全在你的瀏覽器裡對隱藏測試執行。程式碼隨打隨存(本地)。Ctrl+Enter 判題。
卡住了?提示
提示 1 —— 為什麼 √n 就夠
如果 n = a × b 且 a ≤ b,那麼 a ≤ √n。大於 √n 的因子總配著一個更小的——所以試到 i * i <= n 就覆蓋全部。
提示 2 —— 邊界情況
n < 2 → 不是素數(迴圈之前處理)。25 這樣的完全平方數需要 i * i <= n 裡的 <=,不是 <——否則 5×5 溜過去。找到因子立刻 break。
解答(先自己試!)
int n = int.Parse(Console.ReadLine());
if (n < 2) { Console.WriteLine("No"); return; }
bool prime = true;
for (int i = 2; i * i <= n; i++)
{
if (n % i == 0) { prime = false; break; }
}
Console.WriteLine(prime ? "Yes" : "No");頂層的 return 提前離場——n < 2 的情況不需要 else。把它擴到“數出 N 以內全部素數”就是篩法——很好的下一站。下一題:斐波那契數。